Cod sursa(job #446035)

Utilizator andrei.12Andrei Parvu andrei.12 Data 24 aprilie 2010 21:09:02
Problema Arbore Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include<stdio.h>
#include<math.h>
#include<bitset>
#include<vector>

using namespace std;

const int lg = 100005, rad = 318;

int n, m, x, y, sq, nxt, ind, cnt, first[rad], last[rad], init[lg][2], who[lg], A[lg], B[rad], suma, X, val, caut, fnd, i, poz[lg], p1, p2, j, k, op;
bool fst[lg];

bitset<1000002> pus[rad];
vector<int> v[lg];

void df(int nod){
	fst[nod] = 1;

	init[nod][0] = ++ cnt; who[cnt] = nod;

	for (int i = 0; i < (int)v[nod].size(); i ++)
		if (!fst[ v[nod][i] ])
			df(v[nod][i]);

	init[nod][1] = cnt;
}

void baga(int p1, int x, int y, int val){
	int j;

	for (j = first[p1]; j <= last[p1]; j ++)
		pus[p1][ A[j] ] = 0;

	for (j = x; j <= y; j ++)
		A[j] += val;

	for (j = first[p1]; j <= last[p1]; j ++)
		pus[p1][ A[j] ] = 1;
}

int main()
{
	freopen("arbore.in", "rt", stdin);
	freopen("arbore.out", "wt", stdout);

	scanf("%d%d", &n, &m);
	for (i = 1; i < n; i ++){
		scanf("%d%d", &x, &y);

		v[x].push_back(y);
		v[y].push_back(x);
	}

	df(1);

	sq = (int)sqrt(n) + 1; nxt = sq; first[1] = 1; ind = 1; pus[1][0] = 1;

	for (i = 1; i <= n; i ++){
		if (i <= nxt)
			poz[i] = ind;

		if (i == nxt){
			last[ind] = i;

			nxt += sq;
			ind ++;

			first[ind] = i + 1; pus[ind][0] = 1;
		}
	}
	last[ind] = n;

	for (i = 1; i <= m; i ++){
		scanf("%d", &op);

		if (op == 1){
			scanf("%d%d", &X, &val);

			x = init[X][0], y = init[X][1];
			p1 = poz[x], p2 = poz[y];

			if (p1 == p2)
				baga(p1, x, y, val);
			else{
				baga(p1, x, last[p1], val);
				baga(p2, first[p2], y, val);

				for (j = p1 + 1; j < p2; j ++)
					B[j] += val;
			}
		}
		else{
			scanf("%d", &suma);

			fnd = -1;
			for (j = 1; j <= sq && fnd == -1; j ++){
				caut = suma - B[j];

				if (caut >= 0)
					if (pus[j][caut] == 1){
						for (k = first[j]; k <= last[j] && fnd == -1; k ++)
							if (A[k] == caut)
								fnd = who[k];
					}
			}
			printf("%d\n", fnd);
		}
	}

	return 0;
}