oj.uz

Submission #106488

# Submission time Handle Problem Language Result Execution time Memory
106488 2019-04-19T00:53:13 Z wilwxk Regions (IOI09_regions) C++11
10 / 100
 508 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][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) 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
10.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 12 ms 9728 KB Time limit exceeded (wall clock)
2 Execution timed out 9 ms 9728 KB Time limit exceeded (wall clock)
3 Execution timed out 12 ms 9984 KB Time limit exceeded (wall clock)
4 Correct 12 ms 10496 KB Output is correct
5 Correct 19 ms 12032 KB Output is correct
6 Execution timed out 14 ms 14208 KB Time limit exceeded (wall clock)
7 Correct 44 ms 16384 KB Output is correct
8 Correct 42 ms 18716 KB Output is correct
9 Correct 72 ms 31572 KB Output is correct
10 Correct 109 ms 52216 KB Output is correct
11 Correct 123 ms 70952 KB Output is correct
12 Correct 207 ms 92696 KB Output is correct
13 Correct 241 ms 107384 KB Output is correct
14 Correct 240 ms 130592 KB Output is correct
15 Runtime error 138 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 142 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 139 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 146 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 214 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 184 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 194 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 222 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 228 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 327 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 392 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 346 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 272 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 336 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 288 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 416 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 508 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 365 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)