Submission #94297

# Submission time Handle Problem Language Result Execution time Memory
94297 2019-01-17T11:48:41 Z ekrem Regions (IOI09_regions) C++
0 / 100
148 ms 49192 KB
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 200005
#define M 25005
#define kok 500
using namespace std;

typedef pair < int , int > ii;
typedef pair < int , ii > iii;

int n, m, q, k, tme, a[N], ne[N], say[N], mi[N], ust[N/kok + 10][M], alt[N/kok + 10][M];
vector < int > g[N];
vector < ii > gez[N];

void bul(int node){
	say[ne[a[node]]]++;
	for(int i = 1; i <= k; i++)
		alt[i][a[node]] += say[i];
	for(int i = 0; i < g[node].size(); i++)
		bul(g[node][i]);
	say[ne[a[node]]]--;
}

void bul2(int node){
	say[a[node]]++;
	if(ne[a[node]]){
		for(int i = 1; i <= m; i++)
			ust[ne[a[node]]][i] += say[i];
	}
	for(int i = 0; i < g[node].size(); i++)
		bul2(g[node][i]);
	say[a[node]]--;
}

void dfs(int node){
	gez[a[node]].pb(mp(++tme, 1));
	for(int i = 0; i < g[node].size(); i++)
		dfs(g[node][i]);
	gez[a[node]].pb(mp(++tme, -1));
}

int main() {
	// freopen("regions.gir", "r", stdin);
	// freopen("regions.cik", "w", stdout);

	scanf("%d %d %d",&n ,&m ,&q);
	scanf("%d",a + 1);
	say[a[1]]++;

	for(int i = 2; i <= n; i++){
		int x;
		scanf("%d %d",&x, a + i);
		say[a[i]]++;
		g[x].pb(i);
	}

	for(int i = 1; i <= m; i++)
		if(say[i] >= kok){
			mi[i] = ++k;
			ne[k] = i;
		}

	memset(say, 0, sizeof say);
	bul(1);
	memset(say, 0, sizeof say);
	bul2(1);
// cout << "AMK" << k << endl;

	// for(int i = 1; i <= k; i++) {
	// 	// cout << "AMK" << endl;
	// 	for(int j = 1; j <= m; j++)
	// 		if(j != ne[i]){
	// 			// bul2(1, ne[i], 0, j, i);
	// 			printf("ust[%d][%d] = %d\n", ne[i], j, ust[i][j]);
	// 			printf("alt[%d][%d] = %d\n", ne[i], j, alt[i][j]);
	// 		}
	// }

	dfs(1);

	for(int i = 1; i <= m; i++) // O(N)
		sort(gez[i].begin(), gez[i].end());

	while(q--){
		int x, y;
		scanf("%d %d",&x, &y);
		if(mi[x]){
			printf("%d\n", alt[mi[x]][y]);
			continue;
		}
		if(mi[y]){
			printf("%d\n", ust[mi[y]][x]);
			continue;
		}



		vector < iii > z; // O(kok)
		int sz1 = gez[x].size(), i = 0;
		int sz2 = gez[y].size(), j = 0;
		// cout << x << " " << sz1 << " , " << y << " " << sz2 << endl;
		while(i < sz1 and j < sz2){
			if(gez[x][i].st < gez[y][j].st){
				z.pb(mp(gez[x][i].st , mp(gez[x][i].nd, x)));
				i++;
			} else{
				z.pb(mp(gez[y][j].st , mp(gez[y][j].nd, y)));
				j++;
			}
		}
		while(i < sz1){
			z.pb(mp(gez[x][i].st , mp(gez[x][i].nd, x)));
			i++;
		}
		while(j < sz2){
			z.pb(mp(gez[y][j].st , mp(gez[y][j].nd, y)));
			j++;
		}
		int crp = 0, ans = 0;
		for(i = 0; i < z.size(); i++){
			if(z[i].nd.nd == x)
				crp += z[i].nd.st;
			else
				ans += crp;
		}
		printf("%d\n", ans/2);
	}

	return 0;
}

Compilation message

regions.cpp: In function 'void bul(int)':
regions.cpp:22:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
regions.cpp: In function 'void bul2(int)':
regions.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
regions.cpp: In function 'void dfs(int)':
regions.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:123:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i = 0; i < z.size(); i++){
              ~~^~~~~~~~~~
regions.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n ,&m ,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",a + 1);
  ~~~~~^~~~~~~~~~~~
regions.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x, a + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x, &y);
   ~~~~~^~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Execution timed out 10 ms 10492 KB Time limit exceeded (wall clock)
2 Execution timed out 8 ms 10488 KB Time limit exceeded (wall clock)
3 Execution timed out 10 ms 10488 KB Time limit exceeded (wall clock)
4 Execution timed out 10 ms 10488 KB Time limit exceeded (wall clock)
5 Execution timed out 9 ms 10488 KB Time limit exceeded (wall clock)
6 Execution timed out 9 ms 10488 KB Time limit exceeded (wall clock)
7 Execution timed out 9 ms 10616 KB Time limit exceeded (wall clock)
8 Execution timed out 9 ms 10616 KB Time limit exceeded (wall clock)
9 Execution timed out 10 ms 11128 KB Time limit exceeded (wall clock)
10 Execution timed out 13 ms 11048 KB Time limit exceeded (wall clock)
11 Execution timed out 16 ms 11384 KB Time limit exceeded (wall clock)
12 Execution timed out 18 ms 11896 KB Time limit exceeded (wall clock)
13 Execution timed out 20 ms 11640 KB Time limit exceeded (wall clock)
14 Execution timed out 23 ms 12280 KB Time limit exceeded (wall clock)
15 Execution timed out 23 ms 14712 KB Time limit exceeded (wall clock)
# Verdict Execution time Memory Grader output
1 Execution timed out 44 ms 15388 KB Time limit exceeded (wall clock)
2 Execution timed out 51 ms 14452 KB Time limit exceeded (wall clock)
3 Execution timed out 46 ms 17268 KB Time limit exceeded (wall clock)
4 Execution timed out 24 ms 12152 KB Time limit exceeded (wall clock)
5 Execution timed out 24 ms 13816 KB Time limit exceeded (wall clock)
6 Runtime error 45 ms 25464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Execution timed out 40 ms 14456 KB Time limit exceeded (wall clock)
8 Runtime error 59 ms 32376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Execution timed out 105 ms 20360 KB Time limit exceeded (wall clock)
10 Execution timed out 81 ms 24440 KB Time limit exceeded (wall clock)
11 Execution timed out 134 ms 19848 KB Time limit exceeded (wall clock)
12 Runtime error 133 ms 34436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 109 ms 34448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 148 ms 36904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 111 ms 39576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 105 ms 47108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 140 ms 49192 KB Execution killed with signal 11 (could be triggered by violating memory limits)