Cod sursa(job #1223016)

Utilizator vendettaSalajan Razvan vendetta Data 25 august 2014 08:51:24
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <iostream>
#include <vector>
#include <set>
#include <unordered_map>
#include <map>
#include <bitset>
using namespace std;

const int NMAX = 100002;
ifstream ff("arbore.in");
ofstream g("arbore.out");
vector<int> gf[NMAX];
int f[NMAX], l[NMAX], seq[NMAX], length = 0, value[NMAX], add[NMAX];
vector< pair<int,int> > bucket;
multiset<int> mySet[318];
//map<int,int>myMap[318];
bool myMap[318][1000001];
int used[NMAX];
int n, m, sqrtN;
bitset<1000001> viz[318];

void dfs(int node){
	used[node] = 1;
	f[node] = ++length;
	seq[length] = node;
	for(int i=0; i<gf[node].size(); ++i){
		if (used[gf[node][i]] == 0){
			dfs(gf[node][i]);
		}
	}
	l[node] = length;
}

int main() {
	//freopen("arbore.in", "r", stdin);
	//freopen("arbore.out", "w", stdout);
	ff >> n >> m;
	for(int i=1; i<n; ++i){
		int x, y; 
		ff >> x >> y;
		gf[x].push_back(y);
		gf[y].push_back(x);
	}
	dfs(1);
	sqrtN = 1;
	//n = 100000;
	for(; sqrtN*sqrtN <= n; ++sqrtN);
	for(int i=1, j=1; i<=n; i+=sqrtN, ++j){
		bucket.push_back( make_pair(i, min(n,i+sqrtN-1) ) );
	//	cout << j << "  " << i << " " << min(n, i+sqrtN-1) << "\n";
 	}
	for(int i=0; i<bucket.size(); ++i){
		viz[i][0] = 1;
	}
	for(int i=1; i<=m; ++i){
		int tip; 
		ff >> tip;
		if (tip == 1){
			int s, p;
			ff >> p >> s;
			for(int i=0; i<(int)bucket.size(); ++i){
				if ( bucket[i].first > l[p] || bucket[i].second < f[p] ) continue;
				if ( bucket[i].first >= f[p] && bucket[i].second <= l[p]  ){
					add[i] += s;
					continue;
				}
				for(int j=max(bucket[i].first, f[p]); j<=min(bucket[i].second, l[p]); ++j){
					//mySet[i].erase(mySet[i].find( value[seq[j]] ));
					//myMap[i][ value[seq[j]] ]--;
					viz[i][ value[seq[j]] ] = 0;
					value[seq[j]] += s; 
					//myMap[i][ value[seq[j]] ]++;
					//mySet[i].insert( value[seq[j]] );
				}
				for(int j=bucket[i].first; j<=bucket[i].second; ++j){
					viz[i][ value[seq[j]] ] = 1;
				}
			}
		}else{
			int s;
			ff >> s;
			bool gasit = false;
			for(int i=0; i<(int)bucket.size(); ++i){
				//multiset<int>::iterator it = mySet[i].find(s-add[i]);
				//if (it == mySet[i].end()) continue;
				if (s-add[i] < 0 || viz[i][s-add[i]] == 0) continue;
				gasit = true;
				for(int j=bucket[i].first; j<=bucket[i].second; ++j){
					if (value[ seq[j] ] + add[i] == s){
						g << seq[j] << "\n";
						break;
					}
				}
				break;
			}
			if (!gasit) g << -1 << "\n";
		}
	}
	
	return 0;
}