oj.uz

답안 #94289

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94289 2019-01-17T10:38:50 Z ekrem Regions (IOI09_regions) C++
0 / 100
 8000 ms 38172 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 400005
#define M 25005
#define kok 4000
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 14 ms 19064 KB Time limit exceeded (wall clock)
2 Execution timed out 17 ms 19064 KB Time limit exceeded (wall clock)
3 Execution timed out 16 ms 19064 KB Time limit exceeded (wall clock)
4 Execution timed out 17 ms 19192 KB Time limit exceeded (wall clock)
5 Execution timed out 16 ms 19064 KB Time limit exceeded (wall clock)
6 Execution timed out 16 ms 19192 KB Time limit exceeded (wall clock)
7 Execution timed out 14 ms 19192 KB Time limit exceeded (wall clock)
8 Execution timed out 15 ms 19192 KB Time limit exceeded (wall clock)
9 Execution timed out 16 ms 19704 KB Time limit exceeded (wall clock)
10 Execution timed out 20 ms 19576 KB Time limit exceeded (wall clock)
11 Execution timed out 19 ms 19960 KB Time limit exceeded (wall clock)
12 Execution timed out 21 ms 20472 KB Time limit exceeded (wall clock)
13 Execution timed out 25 ms 20216 KB Time limit exceeded (wall clock)
14 Execution timed out 31 ms 20856 KB Time limit exceeded (wall clock)
15 Execution timed out 31 ms 23544 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2162 ms 24264 KB Time limit exceeded (wall clock)
2 Execution timed out 2670 ms 23080 KB Time limit exceeded (wall clock)
3 Execution timed out 1534 ms 26484 KB Time limit exceeded (wall clock)
4 Execution timed out 28 ms 20856 KB Time limit exceeded (wall clock)
5 Execution timed out 32 ms 22476 KB Time limit exceeded (wall clock)
6 Execution timed out 34 ms 22008 KB Time limit exceeded (wall clock)
7 Execution timed out 44 ms 23160 KB Time limit exceeded (wall clock)
8 Execution timed out 51 ms 28024 KB Time limit exceeded (wall clock)
9 Execution timed out 83 ms 29032 KB Time limit exceeded (wall clock)
10 Execution timed out 98 ms 33144 KB Time limit exceeded (wall clock)
11 Execution timed out 116 ms 28548 KB Time limit exceeded (wall clock)
12 Execution timed out 8074 ms 26016 KB Time limit exceeded
13 Execution timed out 8077 ms 26584 KB Time limit exceeded
14 Execution timed out 8085 ms 25720 KB Time limit exceeded
15 Execution timed out 8084 ms 30604 KB Time limit exceeded
16 Execution timed out 8077 ms 38172 KB Time limit exceeded
17 Execution timed out 8066 ms 36732 KB Time limit exceeded