Submission #53547

# Submission time Handle Problem Language Result Execution time Memory
53547 2018-06-30T07:45:57 Z 김세빈(#1419) Regions (IOI09_regions) C++11
0 / 100
8000 ms 74084 KB
#include <bits/stdc++.h>

using namespace std;

vector <int> V[202020], X[202020], K[25252];
vector <int> S, st;
int A[505][25252], B[505][25252];
int dep[202020], P[202020][20];
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++){
		P[V[p][i]][0]= p;
		dep[V[p][i]] = dep[p] + 1;
		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;
}

void dfs_query(int &ans, int a, int b, int p, int d)
{
	int i;
	
	if(T[p] == a) d ++;
	else if(T[p] == b) ans += d;
	
	for(i=0;i<X[p].size();i++){
		dfs_query(ans, a, b, X[p][i], d);
		X[X[p][i]].clear();
	}
}

int lca(int a, int b)
{
	int i;
	
	if(dep[a] < dep[b]) swap(a, b);
	
	for(i=0;i<=18;i++){
		if(dep[a] - dep[b] & (1<<i)) a = P[a][i];
	}
	
	if(a == b) return a;
	
	for(i=18;i>=0;i--){
		if(P[a][i] != P[b][i]) a = P[a][i], b = P[b][i];
	}
	
	return P[a][0];
}

int query(int a, int b)
{
	int i,j,ret;
	
	S.clear();
	st.clear();
	
	for(i=0,j=0; i<K[a].size() || j<K[b].size();){
		if(i == K[a].size() || (j != K[b].size() && L[K[a][i]] > L[K[b][j]])) S.push_back(K[b][j++]);
		else S.push_back(K[a][i++]);
	}
	
	for(i=0;i<S.size()-1;i++){
		j = lca(S[i], S[i+1]);
		if(j != S[i] && j != S[i+1]) S.push_back(j);
	}
	
	sort(S.begin(), S.end(), comp_L);
	S.erase(unique(S.begin(), S.end()), S.end());
	
	for(i=0;i<S.size();i++){
		for(;!st.empty() && R[st.back()] < L[S[i]]; st.pop_back());
		if(!st.empty()){
		X[st.back()].push_back(S[i]);
	}
		st.push_back(S[i]);
	}
	
	dfs_query(ret, a, b, S[0], 0);
	X[S[0]].clear();
	
	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<=18;i++){
		for(j=1;j<=n;j++){
			P[j][i] = P[P[j][i-1]][i-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:20: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:42:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<V[p].size();i++){
          ~^~~~~~~~~~~~
regions.cpp: In function 'void dfs_query(int&, int, int, int, int)':
regions.cpp:60:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<X[p].size();i++){
          ~^~~~~~~~~~~~
regions.cpp: In function 'int lca(int, int)':
regions.cpp:73:13: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   if(dep[a] - dep[b] & (1<<i)) a = P[a][i];
      ~~~~~~~^~~~~~~~
regions.cpp: In function 'int query(int, int)':
regions.cpp:92: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:92: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:93:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i == K[a].size() || (j != K[b].size() && L[K[a][i]] > L[K[b][j]])) S.push_back(K[b][j++]);
      ~~^~~~~~~~~~~~~~
regions.cpp:93:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i == K[a].size() || (j != K[b].size() && L[K[a][i]] > L[K[b][j]])) S.push_back(K[b][j++]);
                           ~~^~~~~~~~~~~~~~
regions.cpp:97:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<S.size()-1;i++){
          ~^~~~~~~~~~~
regions.cpp:105:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<S.size();i++){
          ~^~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:125: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:127:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", T+1);
  ~~~~~^~~~~~~~~~~
regions.cpp:131: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:154:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 10488 KB Output isn't correct
2 Incorrect 11 ms 10552 KB Output isn't correct
3 Incorrect 13 ms 10552 KB Output isn't correct
4 Incorrect 17 ms 10552 KB Output isn't correct
5 Incorrect 21 ms 10704 KB Output isn't correct
6 Runtime error 31 ms 21308 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Incorrect 60 ms 21352 KB Unexpected end of file - int32 expected
8 Incorrect 63 ms 21352 KB Unexpected end of file - int32 expected
9 Incorrect 110 ms 22140 KB Unexpected end of file - int32 expected
10 Incorrect 348 ms 22588 KB Unexpected end of file - int32 expected
11 Incorrect 789 ms 23624 KB Unexpected end of file - int32 expected
12 Incorrect 663 ms 24728 KB Unexpected end of file - int32 expected
13 Incorrect 1098 ms 24728 KB Unexpected end of file - int32 expected
14 Incorrect 2781 ms 25700 KB Unexpected end of file - int32 expected
15 Incorrect 2819 ms 29572 KB Unexpected end of file - int32 expected
# Verdict Execution time Memory Grader output
1 Execution timed out 8051 ms 33524 KB Time limit exceeded
2 Execution timed out 8023 ms 33524 KB Time limit exceeded
3 Execution timed out 8022 ms 37456 KB Time limit exceeded
4 Incorrect 2582 ms 37456 KB Unexpected end of file - int32 expected
5 Incorrect 1674 ms 37456 KB Unexpected end of file - int32 expected
6 Incorrect 822 ms 37456 KB Unexpected end of file - int32 expected
7 Execution timed out 8042 ms 37456 KB Time limit exceeded
8 Incorrect 3941 ms 49904 KB Unexpected end of file - int32 expected
9 Execution timed out 8087 ms 49904 KB Time limit exceeded
10 Execution timed out 8045 ms 74084 KB Time limit exceeded
11 Execution timed out 8085 ms 74084 KB Time limit exceeded
12 Execution timed out 8029 ms 74084 KB Time limit exceeded
13 Execution timed out 8064 ms 74084 KB Time limit exceeded
14 Execution timed out 8034 ms 74084 KB Time limit exceeded
15 Execution timed out 8034 ms 74084 KB Time limit exceeded
16 Execution timed out 8071 ms 74084 KB Time limit exceeded
17 Execution timed out 8018 ms 74084 KB Time limit exceeded