Advertisement
Guest User

Untitled

a guest
Jul 16th, 2018
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.02 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1e5+7;
  4. struct edge{
  5. int x;
  6. long long cost;
  7. edge(int _x=0,long long _c=0ll):x(_x),cost(_c){}
  8. void read(){
  9. scanf("%d %lld",&x,&cost);
  10. }
  11. };
  12. edge l[N],r[N];
  13. edge p[N];
  14. int main(){
  15. //freopen("input.txt","r",stdin);
  16. int n;
  17. cin>>n;
  18. for(int i=1;i<=n;++i){
  19. l[i].read();
  20. r[i].read();
  21. if(l[i].x!=0){
  22. p[l[i].x]=edge(i,l[i].cost);
  23. }
  24. if(r[i].x!=0){
  25. p[r[i].x]=edge(i,r[i].cost);
  26. }
  27. }
  28. int v;
  29. cin>>v;
  30. long long ans=0;
  31. while(true){
  32. if(p[v].x==0){
  33. break;
  34. }
  35. int ls=v;
  36. v=p[v].x;
  37. if(ans+1>p[ls].cost){
  38. cout<<-1<<endl;
  39. return 0;
  40. }
  41. if(ls==r[v].x){
  42. ans+=max(l[v].cost-(r[v].cost-ans)+1ll,0ll);
  43. }
  44. else{
  45. ans+=max(r[v].cost-(l[v].cost-ans),0ll);
  46. }
  47. }
  48. cout<<ans+1<<endl;
  49. return 0;
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement