oj.uz

Submission #106490

# Submission time Handle Problem Language Result Execution time Memory
106490 2019-04-19T00:59:30 Z wilwxk Regions (IOI09_regions) C++11
0 / 100
 563 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 9776 KB Time limit exceeded (wall clock)
2 Execution timed out 9 ms 9856 KB Time limit exceeded (wall clock)
3 Execution timed out 11 ms 10108 KB Time limit exceeded (wall clock)
4 Incorrect 15 ms 10496 KB Output isn't correct
5 Incorrect 17 ms 11952 KB Output isn't correct
6 Execution timed out 15 ms 14208 KB Time limit exceeded (wall clock)
7 Incorrect 35 ms 16384 KB Output isn't correct
8 Incorrect 54 ms 18816 KB Output isn't correct
9 Incorrect 80 ms 31532 KB Output isn't correct
10 Incorrect 130 ms 52156 KB Output isn't correct
11 Incorrect 160 ms 71064 KB Output isn't correct
12 Incorrect 243 ms 92696 KB Output isn't correct
13 Incorrect 238 ms 107380 KB Output isn't correct
14 Incorrect 264 ms 130612 KB Output isn't correct
15 Runtime error 134 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 143 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 145 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 177 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 148 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 185 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 209 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 401 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 464 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 374 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 265 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 349 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 321 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 458 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 563 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 414 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)