oj.uz

Submission #106487

# Submission time Handle Problem Language Result Execution time Memory
106487 2019-04-19T00:45:12 Z wilwxk Regions (IOI09_regions) C++11
10 / 100
 576 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=2e5+5;
const int MAXC=25005;
const int T=200;
vector<int> g[MAXN];
int cor[MAXN], tam[MAXN], ind[MAXN], indg[MAXN];
int dp[MAXN][1005];
int precalc[1005][MAXN];
vector<int> v, lista[MAXN], grandes;
int n, r, q;

void dfs(int cur, int p) {
	tam[cur]=1; 
	ind[cur]=v.size();
	v.push_back(cor[cur]);

	for(int i=1; i<grandes.size(); i++) dp[cur][i]=dp[p][i];
	if(cur!=p) dp[cur][indg[cor[p]]]++;

	for(auto viz : g[cur]) {
		if(viz==p) continue;
		dfs(viz, cur);
		tam[cur]+=tam[viz];
	}
}

int main() {
	scanf("%d %d %d", &n, &r, &q);

	grandes.push_back(0);
	for(int i=1; i<=n; i++) {
		int a;
		if(i!=1)scanf("%d %d", &a, &cor[i]);
		else scanf("%d", &cor[i]);
		if(i!=1) g[i].push_back(a), g[a].push_back(i);
		lista[cor[i]].push_back(i);

		if(lista[cor[i]].size()==1) grandes.push_back(cor[i]), indg[cor[i]]=grandes.size()-1;
	}

	v.push_back(0);
	dfs(1, 1);
	// for(int i=1; i<=n; i++) {
	// 	printf("vertice %d: tam %d // cor %d // ind %d\n   ", i, tam[i], cor[i], ind[i]);
	// 	for(int j=1; j<grandes.size(); j++) printf("%d ", dp[i][j]); printf("\n");
	// }

	for(int i=1; i<=n; i++) {
		for(int j=1; j<grandes.size(); j++) {
			precalc[j][cor[i]]+=dp[i][j];
			// printf("precalc[%d][cor[%d]=%d]= %d\n", j, i, cor[i], precalc[j][cor[i]]);
		}
	}

	// for(int i=1; i<=r; i++) printf("cor %d: lista[].size()= %d // indg[]= %d\n", i, lista[i].size(), indg[i]);

	while(q--) {
		int a, b; scanf("%d %d", &a, &b);
		if(indg[a]) {
			printf("%d\n", precalc[indg[a]][b]);
			fflush(stdout);
			continue;
		}
	}

}

Compilation message

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:19:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<grandes.size(); i++) dp[cur][i]=dp[p][i];
               ~^~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:51:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=1; j<grandes.size(); j++) {
                ~^~~~~~~~~~~~~~~
regions.cpp:30: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:35:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   if(i!=1)scanf("%d %d", &a, &cor[i]);
           ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:36:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   else scanf("%d", &cor[i]);
        ~~~~~^~~~~~~~~~~~~~~
regions.cpp:60: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);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10 ms 9984 KB Time limit exceeded (wall clock)
2 Execution timed out 11 ms 9856 KB Time limit exceeded (wall clock)
3 Execution timed out 9 ms 9984 KB Time limit exceeded (wall clock)
4 Correct 13 ms 10624 KB Output is correct
5 Correct 18 ms 12032 KB Output is correct
6 Execution timed out 15 ms 14592 KB Time limit exceeded (wall clock)
7 Correct 35 ms 16632 KB Output is correct
8 Correct 44 ms 18944 KB Output is correct
9 Correct 71 ms 32000 KB Output is correct
10 Correct 115 ms 52728 KB Output is correct
11 Correct 109 ms 71416 KB Output is correct
12 Correct 196 ms 93164 KB Output is correct
13 Correct 266 ms 107896 KB Output is correct
14 Correct 256 ms 130784 KB Output is correct
15 Runtime error 127 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 154 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 144 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 157 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 231 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 165 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 182 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 205 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 240 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 405 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 461 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 429 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 283 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 338 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 266 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 393 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 576 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 366 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)