| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 761606 | KN200711 | 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 <stdio.h>
#include <stdlib.h>
#define MAX_N 100000
static int A[MAX_N];
static int B[MAX_N];
static int T[MAX_N];
# include <bits/stdc++.h>
# define ll long long
# define fi first
# define se second
using namespace std;
// idenya dfs dua kali
// yang pertama subtree normal, yang kedua dari luar subtree
vector< pair<int, int> > edge[100001];
bool vis[100001];
int ins[100001];
vector<int> pref[100001], suff[100001];
void dfs(int a, int pr) {
vis[a] = 1;
ins[a] = 0;
for(int k=0;k<edge[a].size();k++) {
if(edge[a][k].fi == pr) continue;
dfs(edge[a][k].fi, a);
ins[a] = max(ins[edge[a][k].fi] + edge[a][k].se, ins[a]);
}
}
int cek, ct;
void fn(int a, int pr, int bf) {
// cout<<"a : "<<a<<" "<<bf<<" "<<ins[a]<<endl;
cek = min(cek, max(bf, ins[a]));
ct = max(ct, max(bf, ins[a]));
pref[a].resize(edge[a].size());
suff[a].resize(edge[a].size());
for(int k=0;k<edge[a].size();k++) {
if(edge[a][k].fi == pr) {
if(k == 0) pref[a][k] = 0;
else pref[a][k] = pref[a][k - 1];
} else {
if(k == 0) pref[a][k] = ins[edge[a][k].fi] + edge[a][k].se;
else pref[a][k] = max(pref[a][k-1], ins[edge[a][k].fi] + edge[a][k].se);
}
}
for(int k=edge[a].size() - 1;k>=0;k--) {
if(edge[a][k].fi == pr) {
if(k == edge[a].size() - 1) suff[a][k] = 0;
else suff[a][k] = suff[a][k + 1];
} else {
if(k == edge[a].size() - 1) suff[a][k] = ins[edge[a][k].fi] + edge[a][k].se;
else suff[a][k] = max(suff[a][k+1], ins[edge[a][k].fi] + edge[a][k].se);
}
}
for(int k=0;k<edge[a].size();k++) {
if(edge[a][k].fi == pr) continue;
int mx = 0;
if(k > 0) mx = max(mx, pref[a][k - 1]);
if(k + 1 < edge[a].size()) mx = max(mx, suff[a][k + 1]);
// cout<<"AA : "<<edge[a][k].fi<<" "<<mx<<" "<<edge[a][k].se<<endl;
fn(edge[a][k].fi, a, max(mx, bf) + edge[a][k].se);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int k=0;k<N;k++) {
edge[k].clear();
vis[k] = 0;
}
for(int i=0;i<M;i++) {
edge[A[i]].push_back(make_pair(B[i], T[i]));
edge[B[i]].push_back(make_pair(A[i], T[i]));
}
vector<int> P;
P.clear();
int ans = 0;
for(int i=0;i<N;i++) {
if(!vis[i]) {
cek = 2e9;
ct = 0;
dfs(i, -1);
fn(i, -1, 0);
ans = max(ans, ct);
P.push_back(cek);
// cout<<cek<<endl;
// cout<<ins[i]<<endl;
// cout<<i<<" "<<cek<<endl;
}
}
sort(P.begin(), P.end());
if(P.size() == 1) return max(P[0], ans);
else if(P.size() == 2) return max(P[0] + P[1] + L, ans);
else {
int t1 = P.back() + L + P[P.size() - 2];
int t2 = P[P.size() - 2] + L + L + P[P.size() - 3];
return max(t1, max(t2, ans));
}
}
int main() {
int N, M, L, i;
int res;
scanf("%d%d%d", &N, &M, &L);
for (i = 0; i < M; i++)
scanf("%d%d%d", &A[i], &B[i], &T[i]);
int answer = travelTime(N, M, L, A, B, T);
printf("%d\n", answer);
return 0;
}