답안 #94300 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94300	2019-01-17T11:57:48 Z	ekrem	Regions (IOI09_regions)	C++	0 / 100	958 ms	33728 KB

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[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

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	11 ms	10488 KB	Time limit exceeded (wall clock)
2	Execution timed out	10 ms	10492 KB	Time limit exceeded (wall clock)
3	Execution timed out	10 ms	10488 KB	Time limit exceeded (wall clock)
4	Execution timed out	8 ms	10488 KB	Time limit exceeded (wall clock)
5	Execution timed out	9 ms	10616 KB	Time limit exceeded (wall clock)
6	Execution timed out	10 ms	10492 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	10616 KB	Time limit exceeded (wall clock)
9	Execution timed out	10 ms	11000 KB	Time limit exceeded (wall clock)
10	Execution timed out	14 ms	11000 KB	Time limit exceeded (wall clock)
11	Execution timed out	14 ms	11304 KB	Time limit exceeded (wall clock)
12	Execution timed out	16 ms	11896 KB	Time limit exceeded (wall clock)
13	Execution timed out	18 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	22 ms	14840 KB	Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	41 ms	15348 KB	Time limit exceeded (wall clock)
2	Execution timed out	50 ms	14372 KB	Time limit exceeded (wall clock)
3	Execution timed out	51 ms	17140 KB	Time limit exceeded (wall clock)
4	Execution timed out	23 ms	12152 KB	Time limit exceeded (wall clock)
5	Execution timed out	24 ms	13768 KB	Time limit exceeded (wall clock)
6	Execution timed out	90 ms	14584 KB	Time limit exceeded (wall clock)
7	Execution timed out	49 ms	14456 KB	Time limit exceeded (wall clock)
8	Execution timed out	59 ms	19704 KB	Time limit exceeded (wall clock)
9	Execution timed out	111 ms	20344 KB	Time limit exceeded (wall clock)
10	Execution timed out	80 ms	24440 KB	Time limit exceeded (wall clock)
11	Execution timed out	122 ms	19852 KB	Time limit exceeded (wall clock)
12	Execution timed out	546 ms	21488 KB	Time limit exceeded (wall clock)
13	Execution timed out	472 ms	21876 KB	Time limit exceeded (wall clock)
14	Execution timed out	958 ms	24820 KB	Time limit exceeded (wall clock)
15	Execution timed out	750 ms	25836 KB	Time limit exceeded (wall clock)
16	Execution timed out	585 ms	30704 KB	Time limit exceeded (wall clock)
17	Execution timed out	905 ms	33728 KB	Time limit exceeded (wall clock)

답안 #94300

Compilation message

Subtask #1 0 / 15.0

Subtask #2 0 / 85.0

Subtask #1
0 / 15.0

Subtask #2
0 / 85.0