fork download
copy 
  1. //USACO 2019 December Contest, Gold
  2. //Problem 2. Milk Visits
  3. #include<bits/stdc++.h>
  4. #define int long long
  5. using namespace std;
  6. void usaco(){
  7. 	freopen("milkvisits.in","r",stdin);
  8. 	freopen("milkvisits.out","w",stdout);
  9. }
  10.  
  11. const int N=1e5+5;
  12. vector<int> a[N];
  13. int t[N],ans[N],an[N][21],dep[N],n,m;
  14. vector<tuple<int,int,int>>q[N];
  15. set<int> c[N];
  16. void build(int x,int p){
  17. 	an[x][0]=p;
  18. 	for(int j=1;j<21;j++) an[x][j]=an[an[x][j-1]][j-1];
  19. 	dep[x]=dep[p]+1;
  20. 	for(auto i:a[x]) if(i!=p) build(i,x);
  21. }
  22. int lca(int x,int y){
  23. 	for(int i=20;i>=0;i--){
  24. 		int u=an[y][i];
  25. 		if(dep[u]>=dep[x]) y=u;
  26. 	}
  27. 	if(x==y) return x;
  28. 	for(int i=20;i>=0;i--){
  29. 		if(an[x][i]!=an[y][i]){
  30. 			x=an[x][i]; y=an[y][i];
  31. 		}
  32. 	}
  33. 	return an[x][0];
  34. }
  35.  
  36. void dfs(int x,int p){
  37. 	c[t[x]].insert(dep[x]);
  38. 	for(auto [d,tt,i]:q[x]){
  39. 		if(c[tt].size()&&*c[tt].rbegin()>=d) ans[i]=1;
  40. 	}
  41. 	for(auto i:a[x]){
  42. 		if(i!=p) dfs(i,x);
  43. 	}
  44. 	c[t[x]].erase(dep[x]);
  45. }
  46.  
  47. signed main() {
  48. 	ios::sync_with_stdio(false); cin.tie(nullptr);
  49. 	usaco();
  50. 	cin>>n>>m;
  51. 	for(int i=1;i<=n;i++) cin>>t[i];
  52. 	for(int i=1;i<n;i++){
  53. 		int u,v; cin>>u>>v;
  54. 		a[u].push_back(v);
  55. 		a[v].push_back(u);
  56. 	}
  57. 	build(1,0);
  58. 	for(int i=0;i<m;i++){
  59. 		int u,v,tt; cin>>u>>v>>tt;
  60. 		if(dep[u]>dep[v]) swap(u,v);
  61. 		int g=lca(u,v);
  62. 		if(g==u) q[v].push_back({dep[u],tt,i});
  63. 		else {
  64. 			q[u].push_back({dep[g],tt,i});
  65. 			q[v].push_back({dep[g],tt,i});
  66. 		}
  67. 	}
  68. 	dfs(1,0);
  69. 	for(int i=0;i<m;i++) cout<<ans[i];
  70. }
  71.  
Success #stdin #stdout 0.01s 15556KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/M5O8vH
2019 December, Gold 2
language:
C++ (gcc 8.3)
created:
3 days 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!