Cod sursa(job #529431)

Utilizator ooctavTuchila Octavian ooctav Data 4 februarie 2011 22:41:57
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 kb
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<deque>
#include<queue>
#include<set>
#include<vector>
using namespace std;

#define II inline
#define LL long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fs first
#define ss second
#define mp make_pair
#define pb push_back
#define FOR(i, a, b) 	for(int i = a ; i <= b ; i++)
#define IFOR(i, a, b) 	for(int i = a ; i >= b ; i--)
#define FORIT(it, V) 	for(vector<int> :: iterator it = V.begin() ; it != V.end() ; it++)
#define all(a) a, a + 

const char IN[] = {"arbore.in"};
const char OUT[] = {"arbore.out"};
const int INF = 1000000005;
const double PI  = 3.14159265;
const int NMAX = 100005;
const int SUMMAX = 1000005;
const int SQRT = 350;

int N, M;
vector<int> gi[NMAX], Graf[NMAX];
int renum[NMAX];
int sub[NMAX];
bitset<SUMMAX> e[SQRT];
bitset<NMAX> viz;//aici pare a fi o greseala ?
int a[NMAX], buc[SQRT];
int nr;

void citi()
{
	scanf("%d%d", &N, &M);
	FOR(i, 1, N - 1)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		gi[x].pb(y);
		gi[y].pb(x);
	}
}

void refa(int nod)
{
	renum[nod] = ++nr;
	viz[nod] = 1;
	int cnr = nr;
	FORIT(it, gi[nod])
		if(!viz[*it])
		{
			refa(*it);
			Graf[renum[nod]].pb(renum[*it]);
		}
	sub[cnr] = nr; 
}

void update(int x, int s)
{
	//fac la foruri min() si max()
	int y = sub[x];
	if(x % SQRT)
	{
		FOR(i, x, min(SQRT * (x / SQRT + 1) - 1, y))	e[x/SQRT][a[i]] = 0;
		FOR(i, x, min(SQRT * (x / SQRT + 1) - 1, y))	a[i] += s;
		FOR(i, max((x/SQRT) * SQRT, 1), min(SQRT * (x / SQRT + 1) - 1, N))	e[x/SQRT][a[i]] = 1;
	}
	if(y % SQRT && x/SQRT != y/SQRT)
	{
		FOR(i, max(SQRT * (y / SQRT), x), y)	e[y/SQRT][a[i]] = 0;
		FOR(i, max(SQRT * (y / SQRT), x), y)	a[i] += s;
		FOR(i, max((x/SQRT) * SQRT, 1), min(SQRT * (x / SQRT + 1) - 1, N))	e[x/SQRT][a[i]] = 1;
	}
	FOR(k, (x / SQRT) + 1, (y / SQRT) - 1)
		buc[k] += s;
}

int query(int s)
{
	int k;
	for(k = 0 ; k <= N/SQRT ; k++)
		if(e[k][s - buc[k]])	break;
	FOR(i, max(k * SQRT, 1), min((k + 1) * SQRT, N))
		if(a[i] == s - buc[k])	return i;
	return -1;
}

void apel()
{
	FOR(i, 1, M)
	{
		int iden, l, s;
		scanf("%d", &iden);
		if(iden == 1)
		{
			scanf("%d%d", &l, &s);
			update(renum[l], s);
		}
		else
		{
			scanf("%d", &s);
			printf("%d\n", query(s));
		}
	}
}

int main()
{
	freopen(IN, "r", stdin);
	freopen(OUT, "w", stdout);
	citi();
	viz.reset();
	FOR(k, 1, SQRT - 1)	e[k].reset();
	refa(1);
	apel();
	return 0;
}