fork download
  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
stdin
3
1 2 19
2 3 8
2 3 11
3 1 4
3 1 7
1 2 8
stdout
42