Cod sursa(job #3241408)

Utilizator divadddDavid Curca divaddd Data 30 august 2024 00:09:20
Problema Arbore Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5+2;
const int VMAX = 1e6+2;
using pii = pair<int, int>;
int n,q,k,ord[NMAX],val[NMAX],mars[NMAX];
vector<int> v[NMAX];
pii interval[NMAX];

ifstream fin("arbore.in");
ofstream fout("arbore.out");

void dfs(int nod, int tata = -1){
  ord[++k] = nod;
  interval[nod] = {k, k};
  for(int fiu: v[nod]){
    if(fiu == tata){
      continue;
    }
    dfs(fiu, nod);
  }
  interval[nod].second = k;
}

int main()
{
  fin >> n >> q;
  for(int i = 1; i < n; i++){
    int x, y;
    fin >> x >> y;
    v[x].push_back(y);
    v[y].push_back(x);
  }
  dfs(1);
  while(q--){
    int t, p, s;
    fin >> t;
    if(t == 1){
      fin >> p >> s;
      // update(p, s);
      auto [l, r] = interval[p];
      mars[l] += s;
      mars[r+1] -= s;
    }else{
      fin >> s;
      // find(s);
      bool found = false;
      for(int i = 1; i <= n; i++){
        mars[i] += mars[i-1];
        val[i] += mars[i];
        mars[i-1] = 0;
        if(val[i] == s && !found){
          fout << ord[i] << "\n";
          found = true;
        }
      }
      mars[n] = 0;
      if(!found){
        fout << "-1\n";
      }
    }
  }
  return 0;
}