fork(1) download
copy 
  1. #define IO std::ios::sync_with_stdio(0) 
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define ls o*2
  5. #define rs o*2+1
  6. typedef long long ll;
  7. const int maxn=1e5+10,N=1e6+10;
  8.  
  9. ll sz[maxn*40], sum[maxn*40];
  10.  
  11. int x[maxn],t[maxn];
  12.  
  13. vector<int>g[maxn],dis[maxn];
  14.  
  15. //res is time to eat
  16. ll qu(int o,int l,int r,ll res){
  17. 	if(l==r)return min(res/l,sz[o]);
  18. 	int m=(l+r)/2;
  19. 	//time to eat is more than the time to eat all cookies
  20. 	//of left side, eat all cookies of left side and goto right
  21. 	if(res>sum[ls])return sz[ls]+qu(rs,m+1,r,res-sum[ls]);
  22. 	//else just try to eat maximum you could eat on left side
  23. 	else return qu(ls,l,m,res);
  24. }
  25.  
  26. //tree is built upon time interval, since our queries will be,
  27. //what is no cookies with lowest time to eat in any vertex
  28. //k is time to eat one cookie
  29. //and v is no of cookies in vertex o
  30. void up(int o,int l,int r,int k,int v){
  31. 	sz[o]+=v;   //stores no of cookies we have in vertex o
  32. 	sum[o]+=1ll*k*v;  //stores total time to eat all cookies of vertex o
  33. 	if(l==r)return;   //if l==r nothing left to update, return
  34. 	int m=(l+r)/2;
  35. 	if(k>m) up(rs,m+1,r,k,v);   //if our time segment 1 to k is in right half, go to right
  36. 	else up(ls,l,m,k,v);    //else goto left
  37. }
  38.  
  39. // void print(ll* ar){
  40. //     for(int i=1; i<20; i++){
  41. //         cout<<i<<" "<<ar[i]<<endl;
  42. //     }
  43. //     cout<<endl;
  44. // }
  45.  
  46. ll dfs(int u,ll res){
  47.     //N is maximum time of a cookie to eat 1-1e6
  48.     //build the tree
  49. 	up(1,1,N,t[u],x[u]);
  50. //	print(sz);
  51. //	print(sum);
  52. 	//get minimum time, max cookie
  53. 	ll ans=qu(1,1,N,res),mx=0,mx2=0;
  54. 	for(int i=0;i<g[u].size();i++){
  55. 		ll w=2ll*dis[u][i];     //travel time
  56. 		if(res<w)continue;      //if travel time is larger than left time continue( can't go below this depth in this(i) adj of u)
  57. 		ll tmp=dfs(g[u][i],res-w);      //do dfs
  58. 		if(tmp>mx) mx2=mx,mx=tmp;   //find max and second max out of all neighbours
  59. 		else if(tmp>mx2) mx2=tmp;
  60. 	}
  61. 	up(1,1,N,t[u],-x[u]);   //update tree again( for other recursions in call stack)
  62. 	if(u==1)return max(ans,mx); 
  63. 	else return max(ans,mx2);
  64. }
  65.  
  66. int main(){
  67. 	IO;
  68. 	int n,u,w;
  69.  
  70. 	ll T;
  71. 	cin>>n>>T;
  72. 	for(int i=1;i<=n;i++)cin>>x[i];
  73. 	for(int i=1;i<=n;i++)cin>>t[i];
  74. 	for(int i=2;i<=n;i++){
  75. 		cin>>u>>w;
  76. 		g[u].push_back(i);
  77. 		dis[u].push_back(w);
  78. 	}
  79. 	cout<<dfs(1,T)<<endl;
  80. }
  81.  
Success #stdin #stdout 0s 83200KB
comments (?)
stdin
copy 
6 74
6 7 8 8 9 4
3 6 8 6 7 10
1 2
2 7
3 9
3 9
2 2
stdout
copy 
13
https://ideone.com/kZAgdk
language:
C++14 (gcc 8.3)
created:
5 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!