Submission #118825

# Submission time Handle Problem Language Result Execution time Memory
118825 2019-06-19T22:46:22 Z wilwxk Regions (IOI09_regions) C++11
0 / 100
104 ms 35524 KB
#include <bits/stdc++.h>
using namespace std;

const int MAXN=2e5+5;
const int MAXC=25000;
vector<int> g[MAXN];
int cor[MAXN], quer[MAXN][2];
unordered_map<int, int> m[MAXN];
map< pair<int, int>, int > resp;
int n, r, q;

void dfs(int z) {
	for(auto viz : g[z]) {
		dfs(viz);
		if(m[viz].size()>m[z].size()) swap(m[viz], m[z]);
		for(auto cur : m[viz]) m[z][cur.first]+=cur.second;
	}
	for(auto cur : m[z]) if(resp.find({cor[z], cur.first})!=resp.end()) resp[{cor[z], cur.first}]+=cur.second;
}

int main() {
	
	scanf("%d %d %d", &n, &r, &q);
	scanf("%d", &cor[1]); m[1][cor[1]]=1;
	for(int i=2; i<=n; i++) {
		int a, b; scanf("%d %d", &a, &b);
		g[a].push_back(i); cor[i]=b;
		m[i][b]=1;
	}
	
	for(int i=0; i<q; i++) {
		int a, b; scanf("%d %d", &a, &b);
		quer[i][0]=a; quer[i][1]=b;
		resp[{a, b}]=0;
	}
	
	dfs(1);
	
	
	for(int i=0; i<q; i++) printf("%d\n", resp[{quer[i][0], quer[i][1]}] );
	
	
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &r, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &cor[1]); m[1][cor[1]]=1;
  ~~~~~^~~~~~~~~~~~~~~
regions.cpp:26:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d %d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~~
regions.cpp:32:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d %d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Execution timed out 13 ms 16000 KB Time limit exceeded (wall clock)
2 Execution timed out 14 ms 16000 KB Time limit exceeded (wall clock)
3 Execution timed out 14 ms 15872 KB Time limit exceeded (wall clock)
4 Execution timed out 13 ms 15872 KB Time limit exceeded (wall clock)
5 Execution timed out 13 ms 16000 KB Time limit exceeded (wall clock)
6 Execution timed out 14 ms 16128 KB Time limit exceeded (wall clock)
7 Execution timed out 14 ms 16128 KB Time limit exceeded (wall clock)
8 Execution timed out 15 ms 16128 KB Time limit exceeded (wall clock)
9 Execution timed out 17 ms 16384 KB Time limit exceeded (wall clock)
10 Execution timed out 18 ms 16896 KB Time limit exceeded (wall clock)
11 Execution timed out 20 ms 17444 KB Time limit exceeded (wall clock)
12 Execution timed out 23 ms 17920 KB Time limit exceeded (wall clock)
13 Execution timed out 24 ms 17912 KB Time limit exceeded (wall clock)
14 Execution timed out 26 ms 18680 KB Time limit exceeded (wall clock)
15 Execution timed out 31 ms 19832 KB Time limit exceeded (wall clock)
# Verdict Execution time Memory Grader output
1 Execution timed out 46 ms 23120 KB Time limit exceeded (wall clock)
2 Execution timed out 49 ms 22824 KB Time limit exceeded (wall clock)
3 Execution timed out 52 ms 24696 KB Time limit exceeded (wall clock)
4 Execution timed out 25 ms 18692 KB Time limit exceeded (wall clock)
5 Execution timed out 30 ms 19576 KB Time limit exceeded (wall clock)
6 Execution timed out 36 ms 20648 KB Time limit exceeded (wall clock)
7 Execution timed out 44 ms 22440 KB Time limit exceeded (wall clock)
8 Execution timed out 55 ms 25720 KB Time limit exceeded (wall clock)
9 Execution timed out 79 ms 30292 KB Time limit exceeded (wall clock)
10 Execution timed out 89 ms 32504 KB Time limit exceeded (wall clock)
11 Execution timed out 103 ms 32764 KB Time limit exceeded (wall clock)
12 Execution timed out 98 ms 34456 KB Time limit exceeded (wall clock)
13 Execution timed out 101 ms 33928 KB Time limit exceeded (wall clock)
14 Execution timed out 101 ms 34296 KB Time limit exceeded (wall clock)
15 Execution timed out 104 ms 35448 KB Time limit exceeded (wall clock)
16 Execution timed out 104 ms 35524 KB Time limit exceeded (wall clock)
17 Execution timed out 98 ms 35448 KB Time limit exceeded (wall clock)