Cod sursa(job #2766922)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 3 august 2021 21:07:31
Problema Arbore Scor 95
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 2.7 kb
#include <bits/stdc++.h>

using namespace std;

struct InParser {
  FILE * fin;
  char * buff;
  int sp;

  char read_ch() {
    ++sp;
    if (sp == 4096) {
      sp = 0;
      fread(buff, 1, 4096, fin);
    }
    return buff[sp];
  }

  InParser(const char * nume) {
    fin = fopen(nume, "r");
    buff = new char[4096]();
    sp = 4095;
  }

  InParser & operator >> (int & n) {
    char c;
    while (!isdigit(c = read_ch()) && c != '-');
    int sgn = 1;
    if (c == '-') {
      n = 0;
      sgn = -1;
    } else {
      n = c - '0';
    }
    while (isdigit(c = read_ch())) {
      n = 10 * n + c - '0';
    }
    n *= sgn;
    return *this;
  }
};

InParser 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) {
  int nxt = min(n, (bucket_index + 1) * B);
  for (int i = bucket_index * B; i < nxt; ++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 < nxt; ++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';
    }
  }
  fout.close();
  return 0;
}