Submission #420329

#	Time	Username	Problem	Language	Result	Execution time	Memory
420329		faresbasbs	Regions (IOI09_regions)	C++14	100 / 100	4675 ms	39992 KiB

regions

#include <bits/stdc++.h>
using namespace std;
const int sq = 501;
int n,r,q,cnt=1,counter[200001],num[200001],color[200001],in[200001],out[200001];
vector<int> allcl,graph[200001],colors[200001],colors2[200001];
long long ans[501][25001];
bool big[200001];

void dfs(int curr , int par){
	for(int i = 0 ; i < allcl.size() ; i += 1){
		ans[i][color[curr]] += counter[allcl[i]];  
	}
	if(big[color[curr]]){
		counter[color[curr]] += 1;
	}
	colors[color[curr]].push_back(cnt),colors2[color[curr]].push_back(curr);
	in[curr] = cnt++;
	for(auto i : graph[curr]){
		if(i == par){
			continue;
		}
		dfs(i,curr);
	}
	if(big[color[curr]]){
		counter[color[curr]] -= 1;
	}
	out[curr] = cnt-1;
}

int main(){
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	cin >> n >> r >> q >> color[1];
	for(int i = 2 ; i <= n ; i += 1){
		int a;
		cin >> a >> color[i];
		graph[a].push_back(i),graph[i].push_back(a);
	}
	for(int i = 1 ; i <= n ; i += 1){
		num[color[i]] += 1;
	}
	for(int i = 1 ; i <= r ; i += 1){
		if(num[i] >= sq){
			big[i] = 1;
			allcl.push_back(i);
		}
	}
	dfs(1,1);
	for(int i = 0 ; i < q ; i += 1){
		int r1,r2;
		cin >> r1 >> r2;
		if(big[r1]){
			cout << ans[lower_bound(allcl.begin(),allcl.end(),r1)-allcl.begin()][r2] << endl;
		}else{
			long long ret = 0;
			for(auto j : colors2[r1]){
				ret += upper_bound(colors[r2].begin(),colors[r2].end(),out[j])
				-upper_bound(colors[r2].begin(),colors[r2].end(),in[j]);
			}
			cout << ret << endl;
		}
	}
}

Compilation message (stderr)

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:10:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  for(int i = 0 ; i < allcl.size() ; i += 1){
      |                  ~~^~~~~~~~~~~~~~

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