oj.uz

답안 #94290

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94290 2019-01-17T10:52:15 Z ekrem Regions (IOI09_regions) C++
0 / 100
 8000 ms 28840 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, int ne, int say, int dur, int kk){
	if(a[node] == ne)
		say++;
	if(a[node] == dur)
		ust[kk][ne] += say;
	for(int i = 0; i < g[node].size(); i++)
		bul(g[node][i], ne, say, dur, kk);
}

void bul2(int node, int ne, int say, int dur, int kk){
	if(a[node] == ne)
		say++;
	if(a[node] == dur)
		alt[kk][dur] += say;
	for(int i = 0; i < g[node].size(); i++)
		bul2(g[node][i], ne, say, dur, kk);
}

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;
		}

	for(int i = 1; i <= k; i++)
		for(int j = 1; j <= m; j++)
			if(j != ne[i]){
				bul(1, j, 0, ne[i], 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++)
		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;
		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, int, int, int, int)':
regions.cpp:23: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, int, int, int, int)':
regions.cpp:32: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:38: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:114:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i = 0; i < z.size(); i++){
              ~~^~~~~~~~~~
regions.cpp:47: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:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",a + 1);
  ~~~~~^~~~~~~~~~~~
regions.cpp:53: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:80: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 8 ms 9720 KB Time limit exceeded (wall clock)
2 Execution timed out 8 ms 9644 KB Time limit exceeded (wall clock)
3 Execution timed out 8 ms 9648 KB Time limit exceeded (wall clock)
4 Execution timed out 8 ms 9720 KB Time limit exceeded (wall clock)
5 Execution timed out 8 ms 9720 KB Time limit exceeded (wall clock)
6 Execution timed out 9 ms 9848 KB Time limit exceeded (wall clock)
7 Execution timed out 8 ms 9848 KB Time limit exceeded (wall clock)
8 Execution timed out 9 ms 9848 KB Time limit exceeded (wall clock)
9 Execution timed out 10 ms 10232 KB Time limit exceeded (wall clock)
10 Execution timed out 13 ms 10356 KB Time limit exceeded (wall clock)
11 Execution timed out 14 ms 10488 KB Time limit exceeded (wall clock)
12 Execution timed out 14 ms 11128 KB Time limit exceeded (wall clock)
13 Execution timed out 17 ms 10872 KB Time limit exceeded (wall clock)
14 Execution timed out 19 ms 11512 KB Time limit exceeded (wall clock)
15 Execution timed out 22 ms 13944 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2188 ms 14960 KB Time limit exceeded (wall clock)
2 Execution timed out 6702 ms 13732 KB Time limit exceeded (wall clock)
3 Execution timed out 7477 ms 16968 KB Time limit exceeded (wall clock)
4 Execution timed out 21 ms 11512 KB Time limit exceeded (wall clock)
5 Execution timed out 21 ms 13116 KB Time limit exceeded (wall clock)
6 Execution timed out 32 ms 12664 KB Time limit exceeded (wall clock)
7 Execution timed out 38 ms 13688 KB Time limit exceeded (wall clock)
8 Execution timed out 49 ms 18680 KB Time limit exceeded (wall clock)
9 Execution timed out 87 ms 19704 KB Time limit exceeded (wall clock)
10 Execution timed out 79 ms 23800 KB Time limit exceeded (wall clock)
11 Execution timed out 110 ms 19172 KB Time limit exceeded (wall clock)
12 Execution timed out 8032 ms 16504 KB Time limit exceeded
13 Execution timed out 8029 ms 16940 KB Time limit exceeded
14 Execution timed out 8048 ms 16248 KB Time limit exceeded
15 Execution timed out 8029 ms 21192 KB Time limit exceeded
16 Execution timed out 8064 ms 28840 KB Time limit exceeded
17 Execution timed out 8066 ms 27284 KB Time limit exceeded