fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <sys/time.h>
  3.  
  4. using namespace std;
  5.  
  6. long long start_time;
  7.  
  8. void start_clock(){
  9.   struct timeval tv;
  10.   gettimeofday(&tv, NULL);
  11.   start_time=(tv.tv_sec*1000000+tv.tv_usec);
  12. }
  13.  
  14. long long current_clock(){
  15.   struct timeval tv;
  16.   gettimeofday(&tv, NULL);
  17.   long long current_time=(tv.tv_sec*1000000+tv.tv_usec);
  18.   // cout << current_time-start_time << "(us)\n";
  19.   return current_time-start_time;
  20. }
  21.  
  22. unsigned long long xor128(){
  23.   static unsigned long long x=123456789,y=362436069,z=521288629,w=88675123;
  24.   unsigned long long t;
  25.   t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
  26. }
  27.  
  28. using pl=pair<long long,long long>;
  29. using Graph=vector<vector<pl>>;
  30.  
  31. vector<long long> dis(long long v,long long n,Graph &g){
  32.   vector<long long> d(n,8e18);
  33.   queue<long long> q;
  34.   q.push(v);
  35.   d[v]=0;
  36.   while(!q.empty()){
  37.     long long od=q.front();q.pop();
  38.     for(auto &nx : g[od]){
  39.       if(d[nx.first]>4e18){
  40.         d[nx.first]=d[od]+nx.second;
  41.         q.push(nx.first);
  42.       }
  43.     }
  44.   }
  45.   return d;
  46. }
  47.  
  48. int main(){
  49.   start_clock();
  50.  
  51.   ios::sync_with_stdio(false);
  52.   cin.tie(nullptr);
  53.   long long n;
  54.   cin >> n;
  55.   Graph g1(n);
  56.   Graph g2(n);
  57.   Graph g3(n);
  58.   for(long long i=1;i<n;i++){
  59.     long long u,v,w;
  60.     cin >> u >> v >> w;
  61.     u--;v--;
  62.     g1[u].push_back({v,w});
  63.     g1[v].push_back({u,w});
  64.   }
  65.   for(long long i=1;i<n;i++){
  66.     long long u,v,w;
  67.     cin >> u >> v >> w;
  68.     u--;v--;
  69.     g2[u].push_back({v,w});
  70.     g2[v].push_back({u,w});
  71.   }
  72.   for(long long i=1;i<n;i++){
  73.     long long u,v,w;
  74.     cin >> u >> v >> w;
  75.     u--;v--;
  76.     g3[u].push_back({v,w});
  77.     g3[v].push_back({u,w});
  78.   }
  79.  
  80.   set<long long> st;
  81.   vector<long long> lis;
  82.   for(long long i=0;i<n;i++){lis.push_back(i);}
  83.  
  84.   long long res=0;
  85.   long long ct=1;
  86.   long long knd=start_time%2;
  87.  
  88.   while(st.size()<n){
  89.     if(current_clock()>1900000){break;}
  90.  
  91.     long long u;
  92.     while(true){
  93.       swap(lis[xor128()%lis.size()],lis[lis.size()-1]);
  94.       u=lis.back();
  95.       lis.pop_back();
  96.       if(st.find(u)==st.end()){break;}
  97.     }
  98.  
  99.     if(knd==0){
  100.       ct++;
  101.       if(ct==8){ct=1;}
  102.     }
  103.  
  104.     while(true){
  105.       if(current_clock()>1900000){break;}
  106.       st.insert(u);
  107.       vector<long long> d1=dis(u,n,g1);
  108.       vector<long long> d2=dis(u,n,g2);
  109.       vector<long long> d3=dis(u,n,g3);
  110.       long long v=0,f=0;
  111.       if(knd==1){ct=1+(xor128()%7);}
  112.       for(long long i=0;i<n;i++){
  113.         long long cr=d1[i]+d2[i]+d3[i];
  114.         long long cf=0;
  115.         if(ct&1ll){cf+=d1[i];}
  116.         if(ct&2ll){cf+=d2[i];}
  117.         if(ct&4ll){cf+=d3[i];}
  118.         res=max(res,cr);
  119.         if(f<cf){
  120.           v=i;
  121.           f=cf;
  122.         }
  123.       }
  124.       if(st.find(v)!=st.end()){break;}
  125.       u=v;
  126.     }
  127.   }
  128.   cout << res << "\n";
  129.   return 0;
  130. }
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
3
1 2 19
2 3 8
2 3 11
3 1 4
3 1 7
1 2 8
stdout
copy 
42
https://ideone.com/GvXDYl
language:
C++14 (gcc 8.3)
created:
292 days ago
visibility:
secret

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!