oj.uz

Submission #106485

# Submission time Handle Problem Language Result Execution time Memory
106485 2019-04-19T00:40:36 Z wilwxk Regions (IOI09_regions) C++11
10 / 100
 559 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)+3];
int precalc[(MAXN/T)+3][MAXN];
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 %d", &a, &cor[i]);
		else 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:51: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:35:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   if(i!=1)scanf("%d %d", &a, &cor[i]);
           ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:36:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   else scanf("%d", &cor[i]);
        ~~~~~^~~~~~~~~~~~~~~
regions.cpp:60: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 9856 KB Time limit exceeded (wall clock)
2 Execution timed out 10 ms 9776 KB Time limit exceeded (wall clock)
3 Execution timed out 11 ms 9984 KB Time limit exceeded (wall clock)
4 Correct 17 ms 10496 KB Output is correct
5 Correct 32 ms 12032 KB Output is correct
6 Execution timed out 15 ms 14464 KB Time limit exceeded (wall clock)
7 Correct 42 ms 16640 KB Output is correct
8 Correct 49 ms 19072 KB Output is correct
9 Correct 57 ms 32020 KB Output is correct
10 Correct 136 ms 52600 KB Output is correct
11 Correct 149 ms 71420 KB Output is correct
12 Correct 237 ms 92920 KB Output is correct
13 Correct 257 ms 107768 KB Output is correct
14 Correct 224 ms 130544 KB Output is correct
15 Runtime error 137 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 148 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 133 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 136 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 187 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 145 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 184 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 221 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 316 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 400 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 249 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 395 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 264 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 399 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 559 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 443 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)