Cod sursa(job #879857)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 15 februarie 2013 22:16:58
Problema Arbore Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 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;
	
}