| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 430650 | 2021-06-16T18:01:38 Z | muhammad_hokimiyon | Dreaming (IOI13_dreaming) | C++14 | 0 ms | 0 KB |
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 7;
int val,ve;
bool used[maxN];
vector<pair<int, int>> v[maxN];
void dfs(int x, int p, int sum)
{
used[x] = true;
if(sum >= val){
val = sum;
ve = x;
}
for(auto y : v[x]){
if(y.first != p){
dfs(y.first, x, sum + y.second);
}
}
}
int travelTime(int N, int M, int L, vector<int> A, vector<int> B, vector<int> T)
{
for(int i = 0; i < M; i++){
v[A[i]].push_back({B[i], T[i]});
v[B[i]].push_back({A[i], T[i]});
}
vector<int> p(N, -1);
vector<int> d(N, 1e9);
vector<pair<int, int>> X;
for(int i = 0; i < N; i++){
if(!used[i]){
val = ve = 0;
dfs(i, i, 0);
int r1 = ve;
val = ve = 0;
dfs(r1, r1, 0);
int r2 = ve;
queue<int> q;
q.push(r1);
d[r1] = 0;
while(!q.empty()){
int x = q.front();
q.pop();
for(auto y : v[x]){
if(d[y.first] == 1e9){
d[y.first] = d[x] + 1;
p[y.first] = x;
q.push(y.first);
}
}
}
vector<int> pa;
while(r2 != r1){
pa.push_back(r2);
r2 = p[r2];
}
pa.push_back(r1);
int v1 = 0;
int res = 1e9;
for(int j = max(0, (int)pa.size() / 2 - 10); j < min((int)pa.size(), (int)pa.size() / 2 + 10); j++){
int st = pa[j];
queue<int> q;
q.push(st);
map<int, int> d;
int mx = 0;
d[st] = 0;
while(!q.empty()){
int x = q.front();
q.pop();
for(auto y : v[x]){
if(d.find(y.first) == d.end()){
d[y.first] = d[x] + y.second;
q.push(y.first);
mx = max(mx, d[x] + y.second);
}
}
}
if(mx < res){
res = mx;
v1 = st;
}
}
X.push_back({res, v1});
}
}
sort(X.rbegin(), X.rend());
for(int i = 1; i < (int)X.size(); i++){
v[X[0].second].push_back({X[i].second, L});
v[X[i].second].push_back({X[0].second, L});
}
val = ve = 0;
dfs(0, 0, 0);
val = 0;
dfs(ve, ve, 0);
return val;
}