Cod sursa(job #2766919)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 3 august 2021 21:00:08
Problema Arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAXN = 1e5;
const int MAXV = 1e6;
const int B = 320;
int n, q, timer = -1, ver[MAXN], l[MAXN], r[MAXN], v[MAXN];
vector<int> G[MAXN];

struct bucket {
  int offset;
  bitset<1 + MAXV> ap;
} a[B];

int get_bucket(int index) {
  return index / B;
}

void dfs(int u, int p) {
  ver[++timer] = u;
  l[u] = timer;
  for (int v : G[u])
    if (v != p)
      dfs(v, u);
  r[u] = timer;
}

void update(int st, int dr, int bucket_index, int s) {
  for (int i = bucket_index * B; i < min(n, (bucket_index + 1) * B); ++i)
    a[bucket_index].ap[v[i]] = false;
  for (int i = st; i <= dr; ++i)
    v[i] += s;
  for (int i = bucket_index * B; i < min(n, (bucket_index + 1) * B); ++i)
    a[bucket_index].ap[v[i]] = true;
}

int main() {
  fin >> n >> q;
  int cnt_buckets = 0;
  for (int i = 0; i < n; i += B) {
    a[cnt_buckets].ap[0] = true;
    a[cnt_buckets].offset = 0;
    ++cnt_buckets;
  }
  for (int e = 1; e < n; ++e) {
    int u, v;
    fin >> u >> v;
    --u, --v;
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }
  dfs(0, -1);
  for (int i = 0; i < q; ++i) {
    int t;
    fin >> t;
    if (t == 1) {
      int v, s;
      fin >> v >> s;
      --v;
      int st = l[v], dr = r[v], curr_bucket = get_bucket(l[v]);
      if (st % B) {
        ++curr_bucket;
        update(st, min(dr, curr_bucket * B - 1), curr_bucket - 1, s);
      }
      while ((curr_bucket + 1) * B - 1 <= dr)
        a[curr_bucket++].offset += s;
      st = curr_bucket * B;
      if (st <= dr)
        update(st, dr, curr_bucket, s);
    } else {
      int s;
      fin >> s;
      int ans = -2;
      for (int b = 0; b < cnt_buckets; ++b)
        if (s >= a[b].offset && a[b].ap[s - a[b].offset]) {
          for (int j = b * B; ; ++j)
            if (v[j] + a[b].offset == s) {
              ans = ver[j];
              break;
            }
          break;
        }
      fout << ans + 1 << '\n';
    }
  }
  fin.close();
  fout.close();
  return 0;
}