| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 636962 | PagodePaiva | 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>
#define ms(v) memset(v, -1, sizeof v)
#define pb push_back
#define mp make_pair
#define sz size
#define ll long long int
#define pi pair <int,int>
#define itn int
#define fr first
#define sc second
#define srt(v) sort(v.begin(), v.end())
#define rvs(v) reverse(v.begin(), v.end())
#define mod 1000000007
#define INF 1e18
#define N 100010
using namespace std;
int n, m, l;
vector <pi> g[N];
int dist[N];
int dista[N];
int distu[N], distv[N];
int distr[N];
vector <int> centros;
int res = -1;
bool comp(int a, int b){
if(dist[a] > dist[b]) return true;
if(dist[a] < dist[b]) return false;
return a > b;
}
void dfs(int node, int pai){
for(auto v : g[node]){
if(v.fr == pai) continue;
dista[v.fr] = dista[node] + v.sc;
dfs(v.fr, node);
}
return;
}
void dfsu(int node, int pai){
for(auto v : g[node]){
if(v.fr == pai) continue;
distu[v.fr] = distu[node] + v.sc;
dfsu(v.fr, node);
}
return;
}
void dfsv(int node, int pai){
for(auto v : g[node]){
if(v.fr == pai) continue;
distv[v.fr] = distv[node] + v.sc;
dfsu(v.fr, node);
}
return;
}
void build(int x){
if(dist[x] != -1) return;
ms(dista);
dista[x] = 0;
dfs(x, -1);
int u = x;
for(int i = 1;i <= n;i++){
if(dista[u] < dista[i]) u = i;
}
ms(dista);
dfs(u, -1);
int v = u;
for(int i = 1;i <= n;i++){
if(dista[v] < dista[i]) v = i;
}
ms(distu);
ms(distv);
dfsu(u, -1);
dfsv(v, -1);
int cent = 1;
for(int i = 1;i <= n;i++){
dist[i] = max(dist[i], max(distu[i], distv[i]));
if(dist[cent] > dist[i]) cent = i;
}
centros.pb(cent);
return;
}
int solve(){
ms(distr);
distr[1] = 0;
dfs(1, -1);
int u = 1;
for(int i = 1;i <= n;i++){
if(distr[u] < distr[i]) u = i;
}
ms(distr);
dfs(u, -1);
int v = u;
for(int i = 1;i <= n;i++){
if(distr[v] < distr[i]) v = i;
}
ms(distu);
ms(distv);
dfsu(u, -1);
dfsv(v, -1);
int resp = -1;
for(int i = 1;i <= n;i++){
resp = max(resp, max(distu[i], distv[i]));
}
return resp;
}
int travelTime(int k, int M, int L, int A[], int B[], int T[]){
n = k;
m = M;
l = L;
for(int i = 0;i < M;i++){
g[B[i]].pb({A[i], T[i]});
g[A[i]].pb({B[i], T[i]});
}
ms(dist);
for(int i = 1;i <= n;i++){
if(dist[i] == -1){
build(i);
}
}
sort(centros.begin(), centros.end(), comp);
for(int i = 1;i < centros.size();i++){
g[centros[0]].pb({g[centros[i]], l});
g[centros[i]].pb({g[centros[0]], l});
}
res = solve();
return res;
}