Cod sursa(job #907286)

Utilizator mitrutstrutMitrea Andrei Ionut mitrutstrut Data 7 martie 2013 19:43:46
Problema Arbore Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.05 kb
#include <fstream>
#include <vector>
#define nmax 100100
using namespace std;
 
int N,M,Answer,A[nmax],B[nmax];
bool viz[nmax];
vector <int> G[nmax],V;
int S[6*nmax],Max[6*nmax];
 
bool Query(int Nod,int Left,int Right,int Val) {
     
    if((Val-=S[Nod]) == 0) {
        Answer=V[Left-1];
        return 1;
        }
     
    int Mid=(Left+Right)>>1,sw=0;
     
    if(Left!=Right && Val>0 && Max[Nod]-S[Nod]>=Val)
        if((sw=Query(2*Nod,Left,Mid,Val))==0) 
            sw=Query(2*Nod+1,Mid+1,Right,Val);
         
    Val+=S[Nod];
     
    return sw;
     
}
void Update(int Nod,int Left,int Right,int Angajat,int Val) {
     
    if(A[Angajat]<=Left && Right<= B[Angajat])
        S[Nod]+=Val;
    else {
         
        int Mid=(Left+Right)>>1;
         
        if(A[Angajat]<=Mid) Update(2*Nod,Left,Mid,Angajat,Val);
        if(Mid<B[Angajat]) Update(2*Nod+1,Mid+1,Right,Angajat,Val);
         
        }
     
    Max[Nod]=S[Nod]+max(Max[2*Nod],Max[2*Nod+1]);
     
}
void DFS(int Nod) {
     
    viz[Nod]=1;
    V.push_back(Nod);
    A[Nod]=V.size();
     
    for(int i=0;i<G[Nod].size();i++)
        if(!viz[G[Nod][i]])
            DFS(G[Nod][i]);
             
    B[Nod]=V.size();
     
}
void read(ifstream & in) {
     
    int i,x,y;
     
    in>>N>>M;
     
    for(i=1;i<N;i++) {
         
        in>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
         
        }
 
}
int main() {
     
    int tip,Angajat,Val;
    ifstream in("arbore.in");
    ofstream out("arbore.out");
     
    read(in);
    DFS(1);
     
    while(M--) {
         
        in>>tip;
         
        if(tip==1) {
            in>>Angajat>>Val;
            Update(1,1,N,Angajat,Val);
            }
        else {
            in>>Val;
             
            if(Query(1,1,N,Val))
                out<<Answer<<'\n';
            else
                out<<"-1\n";
             
            }
         
        }
     
    in.close();
    out.close();
     
    return 0;
     
}