oj.uz

Submission #94298

# Submission time Handle Problem Language Result Execution time Memory
94298 2019-01-17T11:53:09 Z ekrem Regions (IOI09_regions) C++
0 / 100
 905 ms 32388 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 1000
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[mi[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[mi[a[node]]]--;
}

void bul2(int node){
	say[a[node]]++;
	if(mi[a[node]]){
		for(int i = 1; i <= m; i++)
			ust[mi[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);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9 ms 10492 KB Time limit exceeded (wall clock)
2 Execution timed out 9 ms 10488 KB Time limit exceeded (wall clock)
3 Execution timed out 9 ms 10488 KB Time limit exceeded (wall clock)
4 Execution timed out 9 ms 10404 KB Time limit exceeded (wall clock)
5 Execution timed out 10 ms 10536 KB Time limit exceeded (wall clock)
6 Execution timed out 9 ms 10536 KB Time limit exceeded (wall clock)
7 Execution timed out 9 ms 10488 KB Time limit exceeded (wall clock)
8 Execution timed out 9 ms 10620 KB Time limit exceeded (wall clock)
9 Execution timed out 12 ms 11000 KB Time limit exceeded (wall clock)
10 Execution timed out 13 ms 11128 KB Time limit exceeded (wall clock)
11 Execution timed out 14 ms 11384 KB Time limit exceeded (wall clock)
12 Execution timed out 16 ms 11896 KB Time limit exceeded (wall clock)
13 Execution timed out 19 ms 11604 KB Time limit exceeded (wall clock)
14 Execution timed out 22 ms 12280 KB Time limit exceeded (wall clock)
15 Execution timed out 24 ms 14844 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 46 ms 15328 KB Time limit exceeded (wall clock)
2 Execution timed out 49 ms 14452 KB Time limit exceeded (wall clock)
3 Execution timed out 50 ms 17260 KB Time limit exceeded (wall clock)
4 Execution timed out 21 ms 12200 KB Time limit exceeded (wall clock)
5 Execution timed out 24 ms 13816 KB Time limit exceeded (wall clock)
6 Execution timed out 30 ms 13432 KB Time limit exceeded (wall clock)
7 Execution timed out 42 ms 14456 KB Time limit exceeded (wall clock)
8 Execution timed out 47 ms 19324 KB Time limit exceeded (wall clock)
9 Execution timed out 85 ms 20472 KB Time limit exceeded (wall clock)
10 Execution timed out 80 ms 24344 KB Time limit exceeded (wall clock)
11 Execution timed out 110 ms 19852 KB Time limit exceeded (wall clock)
12 Execution timed out 470 ms 21436 KB Time limit exceeded (wall clock)
13 Execution timed out 433 ms 21556 KB Time limit exceeded (wall clock)
14 Execution timed out 905 ms 23436 KB Time limit exceeded (wall clock)
15 Execution timed out 716 ms 25784 KB Time limit exceeded (wall clock)
16 Execution timed out 574 ms 30660 KB Time limit exceeded (wall clock)
17 Execution timed out 832 ms 32388 KB Time limit exceeded (wall clock)