Submission #53538

# Submission time Handle Problem Language Result Execution time Memory
53538 2018-06-30T07:35:05 Z 김세빈(#1419) Regions (IOI09_regions) C++11
0 / 100
3002 ms 10736 KB
#include <bits/stdc++.h>

using namespace std;

vector <int> V[202020], X[202020], K[25252];
vector <int> S, st;
int A[2020][25252], B[2020][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() > 100){
			N[i] = s ++;
			dfs(i, N[i], 1, 0);
		}
	}
	
	for(;q--;){
		scanf("%d%d", &a, &b);
		if(K[a].size() > 100){
			printf("%d\n",A[N[a]][b]);
		}
		else if(K[b].size() > 100){
			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:121: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: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 3002 ms 10360 KB Output isn't correct
2 Incorrect 2945 ms 10420 KB Output isn't correct
3 Incorrect 2835 ms 10420 KB Output isn't correct
4 Incorrect 2838 ms 10420 KB Output isn't correct
5 Incorrect 2839 ms 10420 KB Output isn't correct
6 Incorrect 2892 ms 10532 KB Output isn't correct
7 Incorrect 2685 ms 10608 KB Output isn't correct
8 Incorrect 2735 ms 10608 KB Output isn't correct
9 Execution timed out 19 ms 10608 KB Time limit exceeded (wall clock)
10 Execution timed out 17 ms 10608 KB Time limit exceeded (wall clock)
11 Execution timed out 17 ms 10608 KB Time limit exceeded (wall clock)
12 Execution timed out 19 ms 10608 KB Time limit exceeded (wall clock)
13 Execution timed out 19 ms 10608 KB Time limit exceeded (wall clock)
14 Execution timed out 19 ms 10608 KB Time limit exceeded (wall clock)
15 Execution timed out 23 ms 10608 KB Time limit exceeded (wall clock)
# Verdict Execution time Memory Grader output
1 Execution timed out 18 ms 10736 KB Time limit exceeded (wall clock)
2 Execution timed out 17 ms 10736 KB Time limit exceeded (wall clock)
3 Execution timed out 17 ms 10736 KB Time limit exceeded (wall clock)
4 Execution timed out 18 ms 10736 KB Time limit exceeded (wall clock)
5 Execution timed out 17 ms 10736 KB Time limit exceeded (wall clock)
6 Execution timed out 23 ms 10736 KB Time limit exceeded (wall clock)
7 Execution timed out 19 ms 10736 KB Time limit exceeded (wall clock)
8 Execution timed out 18 ms 10736 KB Time limit exceeded (wall clock)
9 Execution timed out 19 ms 10736 KB Time limit exceeded (wall clock)
10 Execution timed out 18 ms 10736 KB Time limit exceeded (wall clock)
11 Execution timed out 21 ms 10736 KB Time limit exceeded (wall clock)
12 Execution timed out 17 ms 10736 KB Time limit exceeded (wall clock)
13 Execution timed out 17 ms 10736 KB Time limit exceeded (wall clock)
14 Execution timed out 18 ms 10736 KB Time limit exceeded (wall clock)
15 Execution timed out 19 ms 10736 KB Time limit exceeded (wall clock)
16 Execution timed out 17 ms 10736 KB Time limit exceeded (wall clock)
17 Execution timed out 17 ms 10736 KB Time limit exceeded (wall clock)