oj.uz

Submission #53566

# Submission time Handle Problem Language Result Execution time Memory
53566 2018-06-30T08:21:37 Z 김세빈(#1419) Regions (IOI09_regions) C++11
0 / 100
 8000 ms 6204 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:73:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("input.txt","r",stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8018 ms 5540 KB Time limit exceeded
2 Execution timed out 8029 ms 5692 KB Time limit exceeded
3 Execution timed out 8031 ms 5764 KB Time limit exceeded
4 Execution timed out 8053 ms 5820 KB Time limit exceeded
5 Execution timed out 8069 ms 5820 KB Time limit exceeded
6 Execution timed out 8054 ms 5872 KB Time limit exceeded
7 Execution timed out 8045 ms 5872 KB Time limit exceeded
8 Execution timed out 8061 ms 5872 KB Time limit exceeded
9 Execution timed out 29 ms 5948 KB Time limit exceeded (wall clock)
10 Execution timed out 28 ms 5948 KB Time limit exceeded (wall clock)
11 Execution timed out 28 ms 5952 KB Time limit exceeded (wall clock)
12 Execution timed out 28 ms 5952 KB Time limit exceeded (wall clock)
13 Execution timed out 28 ms 6076 KB Time limit exceeded (wall clock)
14 Execution timed out 30 ms 6076 KB Time limit exceeded (wall clock)
15 Execution timed out 36 ms 6076 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 28 ms 6076 KB Time limit exceeded (wall clock)
2 Execution timed out 29 ms 6076 KB Time limit exceeded (wall clock)
3 Execution timed out 28 ms 6076 KB Time limit exceeded (wall clock)
4 Execution timed out 29 ms 6076 KB Time limit exceeded (wall clock)
5 Execution timed out 29 ms 6076 KB Time limit exceeded (wall clock)
6 Execution timed out 30 ms 6076 KB Time limit exceeded (wall clock)
7 Execution timed out 38 ms 6076 KB Time limit exceeded (wall clock)
8 Execution timed out 28 ms 6076 KB Time limit exceeded (wall clock)
9 Execution timed out 28 ms 6076 KB Time limit exceeded (wall clock)
10 Execution timed out 30 ms 6076 KB Time limit exceeded (wall clock)
11 Execution timed out 31 ms 6076 KB Time limit exceeded (wall clock)
12 Execution timed out 30 ms 6076 KB Time limit exceeded (wall clock)
13 Execution timed out 39 ms 6076 KB Time limit exceeded (wall clock)
14 Execution timed out 33 ms 6076 KB Time limit exceeded (wall clock)
15 Execution timed out 30 ms 6204 KB Time limit exceeded (wall clock)
16 Execution timed out 28 ms 6204 KB Time limit exceeded (wall clock)
17 Execution timed out 32 ms 6204 KB Time limit exceeded (wall clock)