fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define int long long int
  3. using namespace std;
  4. int max_sum=-(int)1e9;
  5. int max_node;
  6. struct node
  7. {
  8.     int val;
  9.     int dis;
  10.     vector<node*>child;
  11.     node* par;
  12.     int prority;
  13. };
  14. int cmp(node* a,node* b)
  15. {
  16.     return a->prority<b->prority;
  17. }
  18. int cmp1(int a,int b)
  19. {
  20.     return a>b;
  21. }
  22. node* Node[(int)1e6];
  23. node* createnode()
  24. {
  25.     node* newnode=(node*)malloc(sizeof(node));
  26.     newnode->child.clear();
  27.     newnode->par=NULL;
  28.     return newnode;
  29. }
  30. void travel_tree(node* root)
  31. {
  32.     if(root==NULL)
  33.     {
  34.         return;
  35.     }
  36.     cout<<root->val<<" "<<root->dis<<" "<<root->prority<<endl;
  37.     for(int i=0;i<root->child.size();i++)
  38.     {
  39.         travel_tree(root->child[i]);
  40.     }
  41. }
  42. int maxs(int a,int b)
  43. {
  44.     if(a>b)return a;
  45.     return b;
  46. }
  47. int checktree(node* root)
  48. {
  49.     if(root==NULL)
  50.     {
  51.         return 0;
  52.     }
  53.     if(root->child.empty())
  54.     {
  55.         if(root->dis>max_sum)
  56.         {
  57.             max_sum=root->dis;
  58.             max_node=root->val;
  59.             //cout<<"max_sum"<<max_sum<<endl;
  60.             //cout<<"max_node"<<max_node<<endl;
  61.         }
  62.         return root->dis;
  63.     }
  64.     //midpoint
  65.     vector<int>dis;
  66.     for(int i=0;i<root->child.size();i++)
  67.     {
  68.         dis.emplace_back(checktree(root->child[i]));
  69.     }
  70.     sort(dis.begin(),dis.end(),cmp1);
  71.     //midpoint
  72.     if(dis.size()>=2&&dis[0]+dis[1]+root->dis>max_sum)
  73.     {
  74.         //cout<<"2"<<endl;
  75.         max_sum=dis[0]+dis[1]+root->dis;
  76.         max_node=root->val;
  77.         //cout<<"max_sum"<<max_sum<<endl;
  78.         //cout<<"max_node"<<max_node<<endl;
  79.     }
  80.     if(dis.size()==1&&dis[0]+root->dis>max_sum)
  81.     {
  82.         //cout<<"1"<<endl;
  83.         max_sum=dis[0]+root->dis;
  84.         max_node=root->val;
  85.         //cout<<"max_sum"<<max_sum<<endl;
  86.         //cout<<"max_node"<<max_node<<endl;
  87.     }
  88.     int max_route;
  89.     if(dis.size()>=2)
  90.     {
  91.         max_route=maxs(dis[0],dis[1]);
  92.     }
  93.     else
  94.     {
  95.         max_route=dis[0];
  96.     }
  97.     if(max_route<0)
  98.     {
  99.         if(root->dis>max_sum)
  100.         {
  101.             max_sum=root->dis;
  102.             max_node=root->val;
  103.             //cout<<"max_sum"<<max_sum<<endl;
  104.             //cout<<"max_node"<<max_node<<endl;
  105.         }
  106.         return root->dis;
  107.     }
  108.     else
  109.     {
  110.         if(root->dis+max_route>max_sum)
  111.         {
  112.             max_sum=root->dis+max_route;
  113.             max_node=root->val;
  114.             //cout<<"max_sum"<<max_sum<<endl;
  115.             //cout<<"max_node"<<max_node<<endl;
  116.         }
  117.         return root->dis+max_route;
  118.     }
  119. }
  120. void solve()
  121. {
  122.      for(int i=0;i<sizeof(Node)/sizeof(node*);i++)
  123.      {
  124.          //cout<<sizeof(Node)/sizeof(node*)<<endl;
  125.          Node[i]=NULL;
  126.      }
  127.      int n,m;
  128.      cin>>n>>m;
  129.      node* root=createnode();
  130.      int val,dis,par;
  131.      cin>>val>>dis;
  132.      root->par=NULL;
  133.      root->val=val;
  134.      root->dis=dis;
  135.      Node[val]=root;
  136.      while(n--)
  137.      {
  138.          int par,val,dis;
  139.          cin>>par>>val>>dis;
  140.          node* newnode;
  141.          if(Node[val]==NULL)
  142.          {
  143.              newnode=createnode();
  144.              newnode->dis=dis;
  145.              newnode->val=val;
  146.              Node[val]=newnode;
  147.          }
  148.          else
  149.          {
  150.              newnode=Node[val];
  151.              newnode->val=val;
  152.              newnode->dis=dis;
  153.          }
  154.          if(Node[par]==NULL)
  155.          {
  156.              node* parentnode=createnode();
  157.              parentnode->child.emplace_back(newnode);
  158.              newnode->par=parentnode;
  159.              parentnode->val=par;
  160.              Node[par]=parentnode;
  161.          }
  162.          else
  163.          {
  164.              Node[par]->child.emplace_back(newnode);
  165.              newnode->par=Node[par];
  166.          }
  167.          newnode->prority=newnode->par->child.size()-1;
  168.      }
  169.      //travel_tree(root);
  170.      while(m--)
  171.  
  172.      {
  173.          string cmd;
  174.          cin>>cmd;
  175.          if(cmd=="Check")
  176.          {
  177.              checktree(root);
  178.              cout<<"Maximum Value: "<<max_sum<<endl;
  179.              cout<<"Root of the Path: "<<max_node<<endl;
  180.              max_sum=-(int)1e9;
  181.          }
  182.          else if(cmd=="Add")
  183.          {
  184.             int par,val,dis;
  185.             cin>>par>>val>>dis;
  186.             node* newnode;
  187.             //cout<<"Add"<<endl;
  188.             if(Node[val]==NULL)
  189.             {
  190.                 newnode=createnode();
  191.                 newnode->dis=dis;
  192.                 newnode->val=val;
  193.                 Node[val]=newnode;
  194.             }
  195.             else
  196.             {
  197.                 newnode=Node[val];
  198.                 newnode->val=val;
  199.                 newnode->dis=dis;
  200.             }
  201.             //cout<<"child"<<endl;
  202.             if(Node[par]==NULL)
  203.             {
  204.                 node* parentnode=createnode();
  205.                 parentnode->child.emplace_back(newnode);
  206.                 newnode->par=parentnode;
  207.                 parentnode->val=par;
  208.                 Node[par]=parentnode;
  209.             }
  210.             else
  211.             {
  212.                 Node[par]->child.emplace_back(newnode);
  213.                 newnode->par=Node[par];
  214.             }
  215.             //cout<<"parent"<<endl;
  216.             newnode->prority=newnode->par->child.size()-1;
  217.          }
  218.          else
  219.          {
  220.              int deletenode;
  221.              cin>>deletenode;
  222.              if(Node[deletenode]!=NULL)
  223.              {
  224.                  //cout<<"deletenode"<<endl;
  225.                  for(auto it=Node[deletenode]->par->child.begin();it!=Node[deletenode]->par->child.end();it++)
  226.                  {
  227.                      //cout<<(*it)->val<<endl;
  228.                      if((*it)->val==Node[deletenode]->val)
  229.                      {
  230.                          for(auto it2=next(it);it2!=Node[deletenode]->par->child.end();it2++)
  231.                          {
  232.                              (*it2)->prority--;
  233.                          }
  234.                          Node[deletenode]->par->child.erase(it);
  235.                          break;
  236.                      }
  237.                  }
  238.                  //cout<<"here"<<endl;
  239.                  for(int i=0;i<Node[deletenode]->child.size();i++)
  240.                  {
  241.                      Node[deletenode]->par->child.emplace_back(Node[deletenode]->child[i]);
  242.                      Node[deletenode]->child[i]->prority=Node[deletenode]->par->child.size()-1;
  243.                      Node[deletenode]->child[i]->par=Node[deletenode]->par;
  244.                  }
  245.                  sort(Node[deletenode]->par->child.begin(),Node[deletenode]->par->child.end(),cmp);
  246.                  free(Node[deletenode]);
  247.                  Node[deletenode]=NULL;
  248.              }
  249.          }
  250.          //travel_tree(root);
  251.      }
  252.      checktree(root);
  253.      //cout<<"Maximum Value: "<<max_sum<<endl;
  254.      cout<<"Final Root: "<<max_node<<endl;
  255.      //cout<<maximum<<endl;
  256. }
  257. signed main(void)
  258. {
  259.     cin.tie(NULL),cout.tie(NULL);
  260.     ios::sync_with_stdio(0);
  261.     solve();
  262. }
Success #stdin #stdout 0.01s 11420KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Final Root: 0
https://ideone.com/hQxPW6
language:
C++14 (gcc 8.3)
created:
16 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!