Submission #1084203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084203		pera	Dreaming (IOI13_dreaming)	C++17	0 / 100	48 ms	21852 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]);
         }
      }
   };
   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);
         max_depths.emplace_back(DFS(i));
      }
   }
   int sz = max_depths.size();
   sort(max_depths.begin() , max_depths.end());
   if(sz == 2){
      return max_depths[0] + max_depths[1] + L;
   }
   return max(max_depths[sz - 1] + max_depths[sz - 2] + L , max_depths[sz - 2] + max_depths[sz - 3] + 2 * L);
}

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