oj.uz

Submission #420277

# Submission time Handle Problem Language Result Execution time Memory
420277 2021-06-08T08:50:35 Z faresbasbs Regions (IOI09_regions) C++14
0 / 100
 162 ms 39932 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] << '\n';
		}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 << '\n';
		}
	}
}

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

# Verdict Execution time Memory Grader output
1 Execution timed out 7 ms 14408 KB Time limit exceeded (wall clock)
2 Execution timed out 8 ms 14408 KB Time limit exceeded (wall clock)
3 Execution timed out 8 ms 14408 KB Time limit exceeded (wall clock)
4 Execution timed out 7 ms 14408 KB Time limit exceeded (wall clock)
5 Execution timed out 7 ms 14408 KB Time limit exceeded (wall clock)
6 Execution timed out 8 ms 14408 KB Time limit exceeded (wall clock)
7 Execution timed out 8 ms 14408 KB Time limit exceeded (wall clock)
8 Execution timed out 8 ms 14536 KB Time limit exceeded (wall clock)
9 Execution timed out 9 ms 14920 KB Time limit exceeded (wall clock)
10 Execution timed out 11 ms 15048 KB Time limit exceeded (wall clock)
11 Execution timed out 13 ms 15172 KB Time limit exceeded (wall clock)
12 Execution timed out 16 ms 15816 KB Time limit exceeded (wall clock)
13 Execution timed out 20 ms 15824 KB Time limit exceeded (wall clock)
14 Execution timed out 18 ms 16072 KB Time limit exceeded (wall clock)
15 Execution timed out 22 ms 19148 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 38 ms 19480 KB Time limit exceeded (wall clock)
2 Execution timed out 47 ms 19008 KB Time limit exceeded (wall clock)
3 Execution timed out 50 ms 21452 KB Time limit exceeded (wall clock)
4 Execution timed out 23 ms 16344 KB Time limit exceeded (wall clock)
5 Execution timed out 23 ms 18120 KB Time limit exceeded (wall clock)
6 Execution timed out 32 ms 17736 KB Time limit exceeded (wall clock)
7 Execution timed out 43 ms 18880 KB Time limit exceeded (wall clock)
8 Execution timed out 49 ms 24384 KB Time limit exceeded (wall clock)
9 Execution timed out 89 ms 24488 KB Time limit exceeded (wall clock)
10 Execution timed out 79 ms 30144 KB Time limit exceeded (wall clock)
11 Execution timed out 129 ms 26804 KB Time limit exceeded (wall clock)
12 Execution timed out 117 ms 25536 KB Time limit exceeded (wall clock)
13 Execution timed out 98 ms 26532 KB Time limit exceeded (wall clock)
14 Execution timed out 162 ms 30016 KB Time limit exceeded (wall clock)
15 Execution timed out 113 ms 31032 KB Time limit exceeded (wall clock)
16 Execution timed out 98 ms 38112 KB Time limit exceeded (wall clock)
17 Execution timed out 125 ms 39932 KB Time limit exceeded (wall clock)