Cod sursa(job #1470100)

Utilizator atatomirTatomir Alex atatomir Data 10 august 2015 13:34:35
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.68 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define foreach(V) for(auto it=V.begin();it!=V.end();it++)
#define fordef(it,a,b) for(it=a;it<=b;it++)
#define mp make_pair
#define pb push_back
#define ll long long
#define pa(a,b) pair< a,b >

#define maxN 100011
#define maxSqrt 350
#define Elem pair<int,int>

#define mod 717
class Hash{
    private:
        vector< Elem > C[mod];
        int getKey(Elem x){
            return (x.first*177)%mod;
        }

    public:
        void init(){
            for(int i=0;i<mod;i++) C[i].clear();
        }
        void add(Elem who){
            C[ getKey(who) ].pb(who);
        }
        void rm(Elem who){
            int key = getKey(who);
            for(int i=0;i<C[key].size();i++){
                if(C[key][i]==who){
                    C[key][i] = C[key][ C[key].size()-1 ];
                    C[key].pop_back();
                    return;
                }
            }
        }
        int Find(int val){
            int key = getKey( mp(val,17) );
            for(auto e:C[key])
                if(e.first==val)
                    return e.second;
            return -1;
        }
};

class Batog{
    private:
        int n,dim;
        int *R;
        int *bonus;
        Hash *Smen;

        int getBlock(int pos){
            return (pos+dim-1)/dim;
        }
        int getStart(int x){
            return dim*(x-1)+1;
        }
        int getStop(int x){
            return min(dim*x,n);
        }
        void changeVal(int pos,int val){
            int actBlock = getBlock(pos);

            Smen[actBlock].rm( mp( R[pos],pos ) );
            R[pos] += val;
            Smen[actBlock].add( mp( R[pos],pos ) );
        }

    public:
        void init(int _n,int *_R,Hash *_Smen,int *_bonus){
            n = _n; R = _R; Smen = _Smen; bonus = _bonus;
            dim = (int)sqrt(1.00*n);

            for(int i=1;i<= getBlock(n) ;i++) {
                Smen[i].init(); bonus[i]=0;
                for(int j = getStart(i); j <= getStop(i) ; j++) Smen[i].add( mp(0,j) );
            }
        }
        void add(int l,int r,int val){
            int fBlock = getBlock(l);
            int lBlock = getBlock(r);

            if(lBlock-fBlock<=1){
                for(int i=l;i<=r;i++) changeVal(i,val);
                return;
            }

            for(int i = l ; i <= getStop(fBlock) ; i++) changeVal(i,val);
            for(int i = getStart(lBlock) ; i <= r ; i++) changeVal(i,val);
            for(int i=fBlock+1;i<lBlock;i++) bonus[i]++;
        }
        int Query(int s){
            int lim = getBlock(n);
            for(int i=1;i<=lim;i++){
                int aux = s - bonus[i];
                int ans = Smen[i].Find(aux);
                if(ans!=-1) return ans;
            }
            return -1;
        }
};

int n,m,i,x,y,cnt,op,s;
vector<int> list[maxN];
bool us[maxN];
int lf[maxN],rh[maxN];

//!----------------------
int R[maxN];
int bonus[maxSqrt];
Hash Smen[maxSqrt];

Batog Work;
//!----------------------


void dfs(int node){
    us[node] = true;
    lf[node] = ++cnt;
    for(auto e:list[node]){
        if(us[e]) continue;
        dfs(e);
    }
    rh[node] = cnt;
}

int main()
{
    freopen("arbore.in","r",stdin);
    freopen("arbore.out","w",stdout);

    scanf("%d %d",&n,&m);
    for(i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        list[x].pb(y);
        list[y].pb(x);
    }

    dfs(1);
    Work.init(n,R,Smen,bonus);

    for(;m--;){
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d",&x,&y);
            Work.add(lf[x],rh[x],y);
        } else {
            scanf("%d",&s);
            printf("%d\n",Work.Query(s));
        }
    }


    return 0;
}