oj.uz

Submission #106491

# Submission time Handle Problem Language Result Execution time Memory
106491 2019-04-19T01:00:32 Z wilwxk Regions (IOI09_regions) C++11
0 / 100
 590 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&&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<=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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10 ms 9856 KB Time limit exceeded (wall clock)
2 Execution timed out 10 ms 9856 KB Time limit exceeded (wall clock)
3 Execution timed out 12 ms 10112 KB Time limit exceeded (wall clock)
4 Incorrect 15 ms 10496 KB Output isn't correct
5 Incorrect 19 ms 11904 KB Output isn't correct
6 Execution timed out 13 ms 14208 KB Time limit exceeded (wall clock)
7 Incorrect 35 ms 16384 KB Output isn't correct
8 Incorrect 27 ms 18688 KB Output isn't correct
9 Incorrect 67 ms 31608 KB Output isn't correct
10 Incorrect 121 ms 52216 KB Output isn't correct
11 Incorrect 155 ms 71080 KB Output isn't correct
12 Incorrect 225 ms 92536 KB Output isn't correct
13 Incorrect 175 ms 107364 KB Output isn't correct
14 Incorrect 218 ms 130404 KB Output isn't correct
15 Runtime error 124 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 142 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 184 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 210 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 229 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 188 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 204 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 251 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 387 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 419 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 402 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 352 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 262 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 387 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 590 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 442 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)