Submission #1013740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013740		huutuan	Dreaming (IOI13_dreaming)	C++14	100 / 100	42 ms	16104 KiB

dreaming

#include "dreaming.h"

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+10;
vector<pair<int, int>> g[N];
int vis[N], n, m, l, dis[N], par[N];
int mx=-1;

void dfs(int u){
   vis[u]=1;
   if (mx==-1 || dis[mx]<dis[u]) mx=u;
   for (auto &e:g[u]){
      int v=e.first, w=e.second;
      if (v==par[u]) continue;
      par[v]=u; dis[v]=dis[u]+w;
      dfs(v);
   }
}

pair<int, int> find_diameter(int u){
   mx=-1; dis[u]=0; par[u]=-1; dfs(u);
   u=mx; mx=-1; dis[u]=0; par[u]=-1; dfs(u);
   int v=mx;
   pair<int, int> ans;
   ans.first=dis[v];
   ans.second=1e9;
   while (v!=-1){
      ans.second=min(ans.second, max(dis[v], dis[mx]-dis[v]));
      v=par[v];
   }
   return ans;
}

int travelTime(int _N, int M, int L, int A[], int B[], int T[]) {
   n=_N, m=M, l=L;
   for (int i=0; i<m; ++i) g[A[i]].emplace_back(B[i], T[i]), g[B[i]].emplace_back(A[i], T[i]);
   vector<pair<int, int>> v;
   for (int i=0; i<n; ++i) if (!vis[i]){
      v.push_back(find_diameter(i));
   }
   if ((int)v.size()==1) return v[0].first;
   if ((int)v.size()==2) return max({v[0].first, v[1].first, v[0].second+v[1].second+l});
   sort(v.begin(), v.end(), [&](pair<int, int> x, pair<int, int> y){ return x.second>y.second; });
   int ans=max(v[0].second+v[1].second+l, v[1].second+v[2].second+l+l);
   for (auto &i:v) ans=max(ans, i.first);
   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