fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define mp make_pair
  4. #define pb push_back
  5. #define lb lower_bound
  6. #define up upper_bound
  7. #define vll vector<ll>
  8. #define G vector<vll >
  9. #define F first
  10. #define S second
  11. #define pll pair<ll,ll>
  12. #define FOR1(i,a) for(i=0;i<=a;i++)
  13. #define FOR2(i,a,b) for(i=a;i<=b;i++)
  14. #define endl '\n'
  15. #define clr(a) memset(a,0,sizeof(a))
  16. #define all(x) x.begin(),x.end()
  17. #define rll read_ll();
  18. #ifndef ONLINE_JUDGE
  19. #define gc getchar
  20. #define pc putchar
  21. #else
  22. #define gc getchar_unlocked
  23. #define pc putchar_unlocked
  24. #endif
  25. typedef long long ll;
  26. ll read_ll(){char c=gc();while((c<'0'||c>'9')&&c!='-')c=gc();ll ret=0;int neg=0;if(c=='-')neg=1,c=gc();while(c>='0'&&c<='9'){ret=10*ret+c-48;c=gc();}return neg?-ret:ret;}
  27. const ll N=10005;
  28. const ll LN=15;
  29.  
  30. struct edge
  31. {
  32. 	ll c,val;
  33. };
  34. vector<vector<edge> > g(N);
  35. ll lvl[N],p[N][LN],secret[N];
  36. bool visited[N];
  37.  
  38. inline ll mpi(ll u,ll v)
  39. {
  40. 	return u*10+v;
  41. }
  42.  
  43. void dfs(ll u)
  44. {
  45. 	int i;
  46. 	FOR2(i,1,LN-1)
  47. 	p[u][i]=p[p[u][i-1]][i-1];
  48. 	for(auto&v:g[u])
  49. 	{
  50. 		if(!visited[v.val])
  51. 		{
  52. 			secret[v.val]=v.c;
  53. 			visited[v.val]=true;
  54. 			p[v.val][0]=u;
  55. 			lvl[v.val]=lvl[u]+1;
  56. 			dfs(v.val);
  57. 		}
  58. 	}
  59. }
  60.  
  61. inline ll lca(ll u,ll v)
  62. {
  63. 	if(lvl[v]>lvl[u]) swap(u,v);
  64.  
  65. 	for(int i=LN-1;i>=0;i--)
  66. 		if(lvl[u]-(1<<i)>=lvl[v])
  67. 			u=p[u][i];
  68. 	if(u==v) return u;
  69. 	for(int i=LN-1;i>=0;i--)
  70. 	if(p[u][i]!=p[v][i])
  71. 		u=p[u][i],v=p[v][i];
  72. 	return p[u][0];
  73. }
  74.  
  75. void solve()
  76. {
  77. 	ll u,v,c,n,m,i; n = rll m=n-1;
  78. 	clr(visited);clr(lvl);
  79. 	pll edgeIndex[n+1];
  80.  
  81. 	edge e;
  82. 	FOR1(i,m-1)
  83. 	g[i].clear();
  84. 	FOR1(i,m-1)
  85. 	{
  86. 		u=rll v=rll c=rll
  87. 		e.val=v; e.c=c;
  88. 		g[u].pb(e);e.val=u;
  89. 		g[v].pb(e);
  90. 		edgeIndex[i+1]=mp(u,v);
  91. 	}
  92. 	dfs(1);
  93. 	string s;
  94. 	while(1)
  95. 	{
  96. 		cin>>s;
  97. 		if(s=="CHANGE")
  98. 		{
  99. 			u=rll v=rll
  100. 			pll pa=edgeIndex[u];
  101. 			if(p[pa.S][0]==pa.F)
  102. 				secret[pa.S]=v;
  103. 			else
  104. 				secret[pa.F]=v;
  105. 		}
  106. 		if(s=="QUERY")
  107. 		{
  108. 			ll center;
  109. 			u=rll v=rll
  110. 			center=lca(u,v);
  111.  
  112. 			ll maxsecret=secret[u],maxsecret2=secret[v];
  113. 			if(center!=u)
  114. 			for(i=LN-1;i>=0;i--)
  115. 			{
  116. 				if(lvl[u]-(1<<i)>lvl[center])
  117. 					if(secret[p[u][i]]>=maxsecret)
  118. 						u=p[u][i],maxsecret=secret[u];
  119. 			}
  120. 			if(center!=v)
  121. 			for(i=LN-1;i>=0;i--)
  122. 			{
  123. 				if(lvl[v]-(1<<i)>lvl[center])
  124. 					if(secret[p[v][i]]>=maxsecret2)
  125. 						v=p[v][i],maxsecret2=secret[v];
  126. 			}
  127. 			cout<<max(maxsecret,maxsecret2)<<endl;
  128. 		}
  129. 		if(s=="DONE")
  130. 			break;
  131. 	}
  132. }
  133.  
  134.  
  135. int main()
  136. {
  137. 	ll t;
  138. 	t=rll
  139. 	while(t--)
  140. 		solve();
  141. 	return 0;
  142. }
Time limit exceeded #stdin #stdout 5s 16816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WZQCbv
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!