| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 976240 | Amaarsaa | Dreaming (IOI13_dreaming) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
//#include "dreaming.h"
using namespace std;
vector < pair < int , int > > adj[100005];
int d[100004], used[100004];
int to[100005];
void dfs(int node, int parent, int dist) {
d[node] = 0;
to[node] = -1;
used[node] = 1;
for ( pair < int, int >& A : adj[node]) {
int child = A.first;
if ( child == parent) continue;
dfs(child, node, dist + A.second);
if ( d[node] < d[child] + A.second) {
d[node] = d[child] + A.second;
to[node] = child;
}
}
}
int ans = 0;
vector < int > Ans;
void Go(int x) {
int y;
dfs(x, x, 0);
while(to[x] != -1) x = to[x];
y = x;
dfs(x, x, 0);
int dist = d[x];
vector < int > v;
while (to[x] != -1) {
v.push_back(x);
x = to[x];
}
v.push_back(x);
int s = 2e9;
for ( int X : v) {
s = min(s, max(d[X], dist -d[X]));
}
ans = max(ans, dist);
Ans.push_back(s);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int i = 0; i < M; i ++) {
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
for (int i = 0; i < N; i ++) {
if (!used[i]) {
Go(i);
}
}
sort(Ans.rbegin(), Ans.rend());
// if ( Ans.size() == 1) return ans;
if ( Ans.size() == 2) return max(ans, Ans[0] + Ans[1] + L);
return max(ans, max(Ans[0] + Ans[1] + L, Ans[1] + Ans[2] + 2 *L));
}