oj.uz

Submission #53571

# Submission time Handle Problem Language Result Execution time Memory
53571 2018-06-30T08:27:34 Z 김세빈(#1419) Regions (IOI09_regions) C++11
100 / 100
 3470 ms 41592 KB 
#include <bits/stdc++.h>

using namespace std;

vector <int> V[202020], K[25252];
vector <int> st;
int A[555][25252], B[555][25252];
int L[202020], R[202020], N[202020], T[202020];
int n, k, cnt, s;

bool comp_L(int ca, int cb) { return L[ca] < L[cb]; }

int dfs_order(int p)
{
	int i;
	
	L[p] = R[p] = cnt++;
	
	for(i=0;i<V[p].size();i++){
		R[p] = dfs_order(V[p][i]);
	}
	
	return R[p];
}

int dfs(int r, int x, int p, int d)
{
	int i, ret;
	
	if(T[p] == r){
		ret = 1;
		d ++;
	}
	else{
		ret = 0;
		A[x][T[p]] += d;
	}
	
	for(i=0;i<V[p].size();i++){
		ret += dfs(r, x, V[p][i], d);
	}
	
	if(T[p] != r){
		B[x][T[p]] += ret;
	}
	
	return ret;
}

int query(int a, int b)
{
	int i,j,ret;
	
	st.clear();
	ret = 0;
	
	for(i=0,j=0; i<K[a].size() || j<K[b].size();){
		if(j == K[b].size() || (i != K[a].size() && L[K[a][i]] < L[K[b][j]])){
			for(;!st.empty() && R[st.back()] < L[K[a][i]]; st.pop_back());
			st.push_back(K[a][i]); i++;
		}
		else{
			for(;!st.empty() && R[st.back()] < L[K[b][j]]; st.pop_back());
			ret += st.size(); j++;
		}
	}
	
	return ret;
}

int main()
{
//	freopen("input.txt","r",stdin);
	
	int i,j,a,b,q;
	
	scanf("%d%d%d", &n, &k, &q);
	
	scanf("%d", T+1);
	K[T[1]].push_back(1);
	
	for(i=2;i<=n;i++){
		scanf("%d%d", &a, T+i);
		V[a].push_back(i);
		K[T[i]].push_back(i);
	}
	
	dfs_order(1);
	
	for(i=1;i<=k;i++){
		sort(K[i].begin(), K[i].end(), comp_L);
		
		if(K[i].size() > 400){
			N[i] = s ++;
			dfs(i, N[i], 1, 0);
		}
	}
	
	for(;q--;){
		scanf("%d%d", &a, &b);
		
		if(K[a].size() > 400){
			printf("%d\n",A[N[a]][b]);
		}
		else if(K[b].size() > 400){
			printf("%d\n",B[N[b]][a]);
		}
		else{
			printf("%d\n",query(a, b));
		}
		
		fflush(stdout);
	}
	
	return 0;
}

Compilation message

regions.cpp: In function 'int dfs_order(int)':
regions.cpp:19:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<V[p].size();i++){
          ~^~~~~~~~~~~~
regions.cpp: In function 'int dfs(int, int, int, int)':
regions.cpp:39:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<V[p].size();i++){
          ~^~~~~~~~~~~~
regions.cpp: In function 'int query(int, int)':
regions.cpp:57:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0,j=0; i<K[a].size() || j<K[b].size();){
               ~^~~~~~~~~~~~
regions.cpp:57:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0,j=0; i<K[a].size() || j<K[b].size();){
                                ~^~~~~~~~~~~~
regions.cpp:58:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(j == K[b].size() || (i != K[a].size() && L[K[a][i]] < L[K[b][j]])){
      ~~^~~~~~~~~~~~~~
regions.cpp:58:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(j == K[b].size() || (i != K[a].size() && L[K[a][i]] < L[K[b][j]])){
                           ~~^~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:75:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j,a,b,q;
        ^
regions.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &k, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", T+1);
  ~~~~~^~~~~~~~~~~
regions.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, T+i);
   ~~~~~^~~~~~~~~~~~~~~~~
regions.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5624 KB Output is correct
2 Correct 7 ms 5812 KB Output is correct
3 Correct 6 ms 5812 KB Output is correct
4 Correct 10 ms 5812 KB Output is correct
5 Correct 8 ms 5812 KB Output is correct
6 Correct 22 ms 5864 KB Output is correct
7 Correct 41 ms 5872 KB Output is correct
8 Correct 41 ms 5872 KB Output is correct
9 Correct 55 ms 6128 KB Output is correct
10 Correct 85 ms 6256 KB Output is correct
11 Correct 126 ms 6640 KB Output is correct
12 Correct 123 ms 6972 KB Output is correct
13 Correct 146 ms 6972 KB Output is correct
14 Correct 186 ms 7228 KB Output is correct
15 Correct 251 ms 9148 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 888 ms 10688 KB Output is correct
2 Correct 1142 ms 10688 KB Output is correct
3 Correct 2048 ms 12988 KB Output is correct
4 Correct 269 ms 12988 KB Output is correct
5 Correct 401 ms 12988 KB Output is correct
6 Correct 672 ms 12988 KB Output is correct
7 Correct 1024 ms 12988 KB Output is correct
8 Correct 1289 ms 24900 KB Output is correct
9 Correct 2068 ms 24900 KB Output is correct
10 Correct 2444 ms 41592 KB Output is correct
11 Correct 3470 ms 41592 KB Output is correct
12 Correct 1249 ms 41592 KB Output is correct
13 Correct 1707 ms 41592 KB Output is correct
14 Correct 2521 ms 41592 KB Output is correct
15 Correct 2469 ms 41592 KB Output is correct
16 Correct 2738 ms 41592 KB Output is correct
17 Correct 2582 ms 41592 KB Output is correct