Submission #1084214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084214		pera	Dreaming (IOI13_dreaming)	C++17	100 / 100	103 ms	31160 KiB

dreaming

#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
int travelTime(int N , int M , int L , int A[] , int B[] , int T[]){
   vector<vector<int>> g(N + 1) , w(N + 1);
   auto add_edge = [&](int u , int v , int weight){
      g[u].emplace_back(v);
      w[u].emplace_back(weight);
   };
   for(int i = 0;i < M;i ++){
      ++A[i],++B[i];
      add_edge(A[i] , B[i] , T[i]);
      add_edge(B[i] , A[i] , T[i]);
   }
   vector<int> visited(N + 1) , d(N + 1) , mx(N + 1) , non_sub(N + 1) , max_depths;
   function<void(int , int)> dfs = [&](int u , int p){
      for(int x = 0;x < (int)g[u].size();x ++){
         if(g[u][x] != p){
            d[g[u][x]] = d[u] + w[u][x];
            dfs(g[u][x] , u);
            mx[u] = max(mx[u] , mx[g[u][x]] + w[u][x]);
         }
      }
   };
   int mxu , s , ans = 0;
   function<void(int , int , int)> go = [&](int u , int p , int D){
      if(mxu == 0 || D >= s){
         mxu = u;
         s = D;
      }
      ans = max(ans , D);
      for(int x = 0;x < (int)g[u].size();x ++){
         if(g[u][x] != p){
            go(g[u][x] , u , D + w[u][x]);
         }
      }
   };
   function<int(int)> DFS = [&](int u){
      visited[u] = 1;
      int mn = max(mx[u] , non_sub[u]);
      multiset<int> X;
      for(int x = 0;x < (int)g[u].size();x ++){
         if(visited[g[u][x]] == 0){
            X.insert(mx[g[u][x]] + w[u][x]);
         }
      }
      for(int x = 0;x < (int)g[u].size();x ++){
         if(visited[g[u][x]] == 0){
            X.erase(X.find(mx[g[u][x]] + w[u][x]));
            non_sub[g[u][x]] = max(non_sub[u] , (X.empty() ? 0 : *--X.end())) + w[u][x];
            mn = min(mn , DFS(g[u][x]));
            X.insert(mx[g[u][x]] + w[u][x]);
         }
      }
      return mn;
   };
   for(int i = 1;i <= N;i ++){
      if(visited[i] == 0){
         dfs(i , -1);
         mxu = s = 0;
         go(i , -1 , 0);
         go(mxu , -1 , 0);
         max_depths.emplace_back(DFS(i));
      }
   }
   int sz = max_depths.size();
   sort(max_depths.begin() , max_depths.end());
   reverse(max_depths.begin() , max_depths.end());
   if(sz == 1){
      return ans;
   }
   if(sz == 2){
      ans = max(ans , max_depths[0] + max_depths[1] + L);
   }else{
      ans = max({ans , max_depths[0] + max_depths[1] + L , max_depths[1] + max_depths[2] + 2 * L});
   }
   return ans;
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23