Cod sursa(job #96)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 4 decembrie 2006 23:43:31
Problema Arbore Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <cstdio>
#include <cmath>
#include <bitset>
#include <vector>
using namespace std;

const int MAXN = 100005;
const int MAXS = 1000001;
const int MAXsqrtN = 350;

int N, M, sqrtN;
vector<int> con[MAXN];
int df[MAXN], l[MAXN], r[MAXN], df0;
int groff[MAXsqrtN], gr0, grl[MAXsqrtN], grr[MAXsqrtN], gr[MAXN], s[MAXN];
bitset<MAXS> grpos[MAXsqrtN];
int u[MAXN];

void dfs(int k)
{
	vector<int> :: iterator it;
	if (u[k]) return;
	u[k] = 1;
	df[df0] = k;
	l[k] = df0++;
	for (it = con[k].begin(); it != con[k].end(); it++)
		dfs(*it);
	r[k] = df0 - 1;
}

void update(int gr, int l, int r, int S)
{
	int i;
	for (i = grl[gr]; i <= grr[gr]; i++)
		grpos[gr][ s[i] ] = 0;
	for (i = l; i <= r; i++)
		s[i] += S;
	for (i = grl[gr]; i <= grr[gr]; i++)
		grpos[gr][ s[i] ] = 1;
}

int main()
{
	freopen("arbore.in", "rt", stdin);
	freopen("arbore.out", "wt", stdout);
	int i, j, k;
	for (scanf("%d %d", &N, &M), sqrtN = (int)sqrt((double)N), i = 1; i < N; i++)
		scanf("%d %d", &j, &k),
		con[j].push_back(k),
		con[k].push_back(j);
	for (i = 1, gr0 = 0; i <= N; i++)
	{
		if (i % sqrtN == 1) { gr0++; grpos[gr0][0] = 1; grl[gr0] = i; grr[gr0 - 1] = i - 1; }
		gr[i] = gr0;
	}
	grr[gr0] = N;
	int S;
	for (dfs(df0 = 1); M; M--)
	{
		scanf("%d", &k);
		if (k == 1)
		{
			scanf("%d %d", &i, &S);
			j = r[i]; i = l[i];
			if (gr[i] == gr[j])
				update(gr[i], i, j, S);
			else
			{
				update(gr[i], i, grr[ gr[i] ], S);
				for (k = gr[i] + 1; k < gr[j]; k++)
					groff[k] += S;
				update(gr[j], grl[ gr[j] ], j, S);
			}
		}
		else
		{
			scanf("%d", &S);
			for (i = 1; i <= gr0; i++)
				if (S >= groff[i] && grpos[i][S - groff[i]])
					break;
			if (i == gr0 + 1) { printf("-1\n"); continue; }
			S -= groff[i];
			for (j = grl[i]; j <= grr[i]; j++)
				if (s[j] == S)
				{
					printf("%d\n", df[j]);
					break;
				}
		}
	}
	return 0;
}