oj.uz

Submission #106489

# Submission time Handle Problem Language Result Execution time Memory
106489 2019-04-19T00:56:04 Z wilwxk Regions (IOI09_regions) C++11
0 / 100
 555 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][(MAXN/T)+5];
int precalc[(MAXN/T)+5][MAXC];
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&&indg[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", &a);
		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:50: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:34:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a; if(i!=1)scanf("%d", &a);
                  ~~~~~^~~~~~~~~~
regions.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &cor[i]);
   ~~~~~^~~~~~~~~~~~~~~
regions.cpp:59: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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10 ms 9728 KB Time limit exceeded (wall clock)
2 Execution timed out 10 ms 9856 KB Time limit exceeded (wall clock)
3 Execution timed out 10 ms 9984 KB Time limit exceeded (wall clock)
4 Execution timed out 10 ms 10496 KB Time limit exceeded (wall clock)
5 Execution timed out 11 ms 11904 KB Time limit exceeded (wall clock)
6 Execution timed out 13 ms 14128 KB Time limit exceeded (wall clock)
7 Execution timed out 14 ms 16384 KB Time limit exceeded (wall clock)
8 Execution timed out 17 ms 18688 KB Time limit exceeded (wall clock)
9 Execution timed out 32 ms 31616 KB Time limit exceeded (wall clock)
10 Execution timed out 65 ms 52092 KB Time limit exceeded (wall clock)
11 Execution timed out 80 ms 71032 KB Time limit exceeded (wall clock)
12 Execution timed out 129 ms 92536 KB Time limit exceeded (wall clock)
13 Execution timed out 127 ms 107384 KB Time limit exceeded (wall clock)
14 Execution timed out 134 ms 130620 KB Time limit exceeded (wall clock)
15 Runtime error 118 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 132 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 132 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 133 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 204 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 193 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 177 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 195 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 243 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 313 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 442 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 431 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 246 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 318 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 289 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 426 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 555 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 441 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)