oj.uz

Submission #106492

# Submission time Handle Problem Language Result Execution time Memory
106492 2019-04-19T01:03:25 Z wilwxk Regions (IOI09_regions) C++11
10 / 100
 565 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<=r; 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<=r; 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 'int main()':
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 9 ms 9728 KB Time limit exceeded (wall clock)
2 Execution timed out 11 ms 9728 KB Time limit exceeded (wall clock)
3 Execution timed out 9 ms 9984 KB Time limit exceeded (wall clock)
4 Correct 11 ms 10496 KB Output is correct
5 Correct 15 ms 11904 KB Output is correct
6 Execution timed out 13 ms 14208 KB Time limit exceeded (wall clock)
7 Correct 26 ms 16512 KB Output is correct
8 Correct 32 ms 18816 KB Output is correct
9 Correct 88 ms 31608 KB Output is correct
10 Correct 137 ms 52148 KB Output is correct
11 Correct 151 ms 71032 KB Output is correct
12 Correct 198 ms 92664 KB Output is correct
13 Correct 237 ms 107512 KB Output is correct
14 Correct 241 ms 130508 KB Output is correct
15 Runtime error 120 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 140 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 154 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 163 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 221 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 197 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 175 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 207 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 264 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 377 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 468 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 430 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 242 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 310 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 294 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 397 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 565 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 423 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)