Cod sursa(job #2384367)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 20 martie 2019 17:54:41
Problema Arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;

const string file = "arbore";
const ll INF = 9223372036854775807ll;
const int inf = 2147483647, B = 400, nmax = 100005;

int n, test, e[nmax], first[nmax], last[nmax], p, add[B+5], v[nmax];
vector<int> g[nmax];
bitset<B> ok[nmax/B+5];

void dfs(int x, int pred = 0)
{
    e[++p] = x;
    first[x] = p;
    for (auto y : g[x])
        if(y != pred)
            dfs(y, x);
    last[x] = p;
}

void resetBucket(int a)
{
    ok[a/B].reset();
    for (int i = (a/B)*B; i/B == a/B && i <= n; ++i){
        v[i] += add[a/B];
        ok[a/B][v[i]] = 1;
    }
    add[a/B] = 0;
}

int main()
{
    ifstream fin (file+".in");
    ofstream fout (file+".out");
    fin >> n >> test;
    for (int i = 1; i < n; ++i){
        int x, y;
        fin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1);
    while(test--){
        int t;
        fin >> t;
        if(t == 1){
            int nod, val;
            fin >> nod >> val;
            int a = first[nod], b = last[nod];
            if(a/B == b/B){
                for (int i = a; i <= b; ++i)
                    v[i] += val;
                resetBucket(a);
            }else{
                for (int i = a; i/B == a/B && i <= n; ++i)
                    v[i] += val;
                resetBucket(a);
                a = ((a+B)/B)*B;
                for (int i = b; i/B == b/B && i >= 1; --i)
                    v[i] += val;
                resetBucket(b);
                b = (b/B)*B;
                while(a != b){
                    add[a] += val;
                    a += B;
                }
            }
        }else{
            int val, ans = -1;
            fin >> val;
            for (int b = 0; b*B <= n; ++b)
                if(ok[b][val-add[b]]){
                    for (int i = b*B; i/B == b && i <= n; ++i)
                        if(v[i]+add[b] == val){
                            ans = e[i];
                            break;
                        }
                    break;
                }
            fout << ans << "\n";
        }
    }
    return 0;
}