Cod sursa(job #993201)

Utilizator raulstoinStoin Raul raulstoin Data 3 septembrie 2013 14:43:25
Problema Arbore Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include<fstream>
#include<bitset>
#include<vector>
#include<cmath>
#include<cstring>

#define NMAX 100002
#define SQRT 320

using namespace std;

ifstream fin("arbore.in");
ofstream fout("arbore.out");

vector<int> G[NMAX];
int n,m,lin[NMAX],first[NMAX],last[NMAX],k,node_val[NMAX];
bool use[NMAX];
bitset<1000001> values[SQRT];

struct piece
{
	int left,right,common;
}v[SQRT];

//
const int SZ=10000;
char input[SZ+1],*in;
  
int atoi()
{
	int nr =0;
	for(;!(*in>='0' && *in<='9') && *in;in++);
  
	if(!*in)
	{
		memset(input,0,sizeof input);
		fin.read(input,SZ);
		in=input;
		for(;!(*in>='0' && *in<='9') && *in;in++);
	}
	for(;*in>='0' && *in<='9';in++)
	{
		nr=nr*10+(*in-'0');
		if(!*(in+1))
		{
			memset(input,0,sizeof input);
			fin.read(input,SZ);
			in=input-1;
		}
	}
	return nr;
}
//


void read()
{
	fin.read(input,SZ);
	in=input;
	n=atoi();
	m=atoi();
	for(int i=1,x,y;i<n;i++)
	{
		x=atoi();
		y=atoi();
		G[x].push_back(y);
		G[y].push_back(x);
	}
}

void DFS(int nod)
{
	use[nod]=1;
	lin[++k]=nod;
	first[nod]=k;
	for(size_t i=0;i<G[nod].size();i++)
		if(!use[G[nod][i]])
			DFS(G[nod][i]);
	last[nod]=k;
}

void split()
{
	k=0;
	for(int i=1,L=(int)sqrtl(n);i<=n;i+=L)
	{
		v[++k].left=i;
		v[k].right=min(i+L-1,n);
		values[k][0]=1;
	}
}

void update(int left,int right,short add)
{
	for(int i=1;i<=k;i++)
	{
		if(v[i].left>right)
			return;
		if(v[i].right<left)
			continue;
		if(left<=v[i].left && v[i].right<=right)
		{
			v[i].common+=add;
			continue;
		}
		for(int j=v[i].left;j<=v[i].right;j++)
		{
			values[i][node_val[j]]=0;
			node_val[j]+=v[i].common;
			if(left<=j && right>=j)
				node_val[j]+=add;
		}
		for(int j=v[i].left;j<=v[i].right;j++)
			values[i][node_val[j]]=1;
		v[i].common=0;
	}
}

int query(int sum)
{
	for(int i=1,Value;i<=k;i++)
	{
		Value=sum-v[i].common;
		if(v[i].common<=sum && values[i][Value])
			for(int j=v[i].left;j<=v[i].right;j++)
				if(Value==node_val[j])
					return lin[j];
	}
	return -1;
}

void solve()
{
	DFS(1);
	split();
	for(int a,b,c;m;m--)
	{
		a=atoi();
		b=atoi();
		if(a==1)
		{
			c=atoi();
			update(first[b],last[b],c);
			continue;
		}
		fout<<query(b)<<'\n';
	}
}

int main()
{
	read();
	solve();
	return 0;
}