| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 815085 | Acanikolic | 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 pb push_back
//#define int long long
#define F first
#define S second
using namespace std;
const int N = 1e5+10;
const int mod = 1e9+7;
const int inf = 1e18;
vector<pair<int,int>>g[N];
vector<long long>all,dist(N),vis(N);
void dfs(int x,int par) {
all.pb(x);
for(auto X:g[x]) {
if(X.F != par) {
dist[X.F] = dist[x] + X.S;
dfs(X.F,x);
}
}
}
pair<int,int>nadji_precnik(int root) {
int x,y;
all.clear();
dist[root] = 0;
dfs(root,0);
int mx = 0,idx = -1;
for(auto X:all) {
if(dist[X] >= mx) {
mx = dist[X];
idx = X;
}
}
x = idx;
mx = 0,idx = -1;
all.clear();
dist[x] = 0;
dfs(x,0);
for(auto X:all) {
//cout << "X = " << X << " dist[x] = " << dist[X] << endl;
if(dist[X] >= mx) {
mx = dist[X];
idx = X;
}
}
//cout << endl;
//cout << idx << endl;
y = idx;
//if(root == 4) cout << "x = " << x << " y = " << y << endl;
return {x,y};
}
void obelezi(int x) {
if(vis[x]) return;
vis[x] = 1;
for(auto X:g[x]) obelezi(X.F);
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]) {
for(int i=0;i<M;i++) {
g[A[i]].pb({B[i],T[i]});
g[B[i]].pb({A[i],T[i]});
}
vector<int>centers;
for(int i=0;i<N;i++) {
if(vis[i]) continue;
//cout << i << endl;
all.clear();
dfs(i,0);
vector<int>all_in_comp = all;
pair<int,int>dia = nadji_precnik(i);
int X = dia.F,Y = dia.S;
//if(i == 4) cout << X << ' ' << Y << endl;
dist[X] = 0;
dfs(X,0);
map<int,int>D;
for(auto XX:all_in_comp) D[XX] = dist[XX];
dist[Y] = 0;
dfs(Y,0);
for(auto XX:all_in_comp) D[XX] = max(D[XX],dist[XX]);
int mn = 1e9,idx = -1;
for(auto XX:all_in_comp) {
if(D[XX] < mn) {
mn = D[XX];
idx = XX;
}
}
//cout << "root = " << i << " dia = " << X << " " << Y << endl;
//cout << "root = " << i << " center = " << idx << endl;
centers.pb(idx);
obelezi(i);
}
for(int i=1;i<centers.size();i++) {
g[centers[0]].pb({centers[i],L});
g[centers[i]].pb({centers[0],L});
}
pair<int,int> res = nadji_precnik(1);
dist[res.F] = 0;
dfs(res.F,0);
int index = 0;
for(int i=0;i<N;i++) {
if(dist[index] <= dist[i]) index = i;
}
return dist[index];
}
/*signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m,l;
cin >> n >> m >> l;
int a[m],b[m],t[m];
for(int i=0;i<m;i++) cin >> a[i];
for(int i=0;i<m;i++) cin >> b[i];
for(int i=0;i<m;i++) cin >> t[i];
cout << travelTime(n,m,l,a,b,t);
return 0;
}*/