oj.uz

Submission #420329

# Submission time Handle Problem Language Result Execution time Memory
420329 2021-06-08T09:51:09 Z faresbasbs Regions (IOI09_regions) C++14
100 / 100
 4675 ms 39992 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14408 KB Output is correct
2 Correct 8 ms 14400 KB Output is correct
3 Correct 10 ms 14408 KB Output is correct
4 Correct 13 ms 14408 KB Output is correct
5 Correct 17 ms 14408 KB Output is correct
6 Correct 28 ms 14408 KB Output is correct
7 Correct 34 ms 14408 KB Output is correct
8 Correct 48 ms 14536 KB Output is correct
9 Correct 57 ms 14936 KB Output is correct
10 Correct 90 ms 15048 KB Output is correct
11 Correct 144 ms 15176 KB Output is correct
12 Correct 138 ms 15816 KB Output is correct
13 Correct 225 ms 15808 KB Output is correct
14 Correct 272 ms 16072 KB Output is correct
15 Correct 260 ms 19076 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2182 ms 19492 KB Output is correct
2 Correct 2334 ms 19068 KB Output is correct
3 Correct 2863 ms 21520 KB Output is correct
4 Correct 312 ms 16328 KB Output is correct
5 Correct 428 ms 18120 KB Output is correct
6 Correct 1283 ms 17732 KB Output is correct
7 Correct 1470 ms 18896 KB Output is correct
8 Correct 1317 ms 24380 KB Output is correct
9 Correct 2345 ms 24600 KB Output is correct
10 Correct 4675 ms 30212 KB Output is correct
11 Correct 3744 ms 26816 KB Output is correct
12 Correct 1391 ms 25548 KB Output is correct
13 Correct 2020 ms 26556 KB Output is correct
14 Correct 2269 ms 30108 KB Output is correct
15 Correct 3975 ms 31104 KB Output is correct
16 Correct 4013 ms 38172 KB Output is correct
17 Correct 3422 ms 39992 KB Output is correct