Submission #94296

#	Time	Username	Problem	Language	Result	Execution time	Memory
94296		ekrem	Regions (IOI09_regions)	C++98	0 / 100	132 ms	47740 KiB

regions

#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][ne[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 (stderr)

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
• Subtask 2: 0 / 85