Submission #152362

#	Time	Username	Problem	Language	Result	Execution time	Memory
152362		groeneprof	Regions (IOI09_regions)	C++14	55 / 100	6711 ms	44748 KiB

regions

#include <bits/stdc++.h>
#define int long long
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
#define V vector
#define pb push_back
#define mp make_pair
using namespace std;
const bool debug = 0;
const int inf = 1e18;

int N, R, Q;
vector<int> par;
vector<vector<int> > children;
vector<int> region;
vector<vector<int> > sets;
vector<int> beg, en;
vector<vector<int> > prec;

void dfs0(int u, int r, int t){
	if(region[u] == r){
		t++;
	}
	else{
		prec[r][u]+=t;
	}
	for(int v : children[u]){
		dfs0(v, r, t);
	}
}

int binsearch(int i, vector<int>& v){
	for(int j : v) H(j);
	int res = -1;
	for(int bs = 1<<20; bs>0; bs/=2){
		//H(bs);
		//H(res+bs);
		//H(v.size());
		//H(v[res+bs]);
		//H(i);
		if(res+bs < v.size() && beg[v[res+bs]] < i){
			res+=bs;
		}		
	}
	P("binsearch "<<i<<" returns "<<res);
	return res;
}

void dfs1(int u, int& stamp){
	beg[u] = stamp++;
	for(int v : children[u]){
		dfs1(v, stamp);
	}
	en[u] = stamp;
}

bool comp(int a, int b){
	return beg[a] < beg[b];
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>N>>R>>Q;
	par.resize(N,0);
	children.resize(N);
	sets.resize(R);
	region.resize(N);
	beg.resize(N);
	en.resize(N);

	cin>>region[0];
	region[0]--;
	sets[region[0]].push_back(0);
	for(int i = 1; i<N; i++){
		int a, b;
		cin>>a>>b;
		a--; b--;
		region[i]=b;
		sets[b].push_back(i);
		par[i]=a;
		children[a].push_back(i);
	}
	vector<int> bigsets(R);
	for(int i = 0; i<R;i++){
		if(sets[i].size()>500) {
			bigsets[i] = prec.size();
			prec.push_back(vector<int>(N, 0));
			dfs0(0, i, 0);
		}
	}
	{
		int stamp = 0;
		dfs1(0, stamp);
	}
	for(int i = 0; i < R; i++){
		sort(sets[i].begin(), sets[i].end(), comp);
	}

	for(int q = 0; q<Q; q++){
		int a, b;
		cin>>a>>b;
		a--; b--;

		if(sets[a].size()>500){
			cout<<prec[bigsets[a]][b]<<endl;
		}
		else{
			int res = 0;
			//P("H");
			for(int i : sets[a]){
				H(i);
				res+=binsearch(en[i], sets[b]) - binsearch(beg[i], sets[b]);
			}
			cout<<res<<endl;
		}
	}

	return 0;
}

Compilation message (stderr)

regions.cpp: In function 'long long int binsearch(long long int, std::vector<long long int>&)':
regions.cpp:49:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(res+bs < v.size() && beg[v[res+bs]] < i){
      ~~~~~~~^~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 40 / 85