| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 551404 | 2022-04-20T15:03:58 Z | razvan | Dreaming (IOI13_dreaming) | C++14 | 0 ms | 0 KB |
#include "dreaming.h"
#include <iostream>
#include <cstdio>
#include <fstream>
#include <vector>
#include <algorithm>
#define pb push_back
using namespace std;
const int maxn = 100005;
struct xy {
int x, y;
};
vector<xy> v[maxn];
int done[maxn];
int bgst[maxn], ibgst[maxn];
//int ibgst2[maxn];
int now = -1, inow;
//int lft, rgh;
int ansnow, iansnow;
void dfs(int x, int p) {
done[x] = true;
int big1 = 0, big2 = 0, ibig1 = -1, ibig2 = -1;
for(auto u : v[x]) {
if(u.x != p) {
dfs(u.x, x);
if(bgst[u.x] + u.y > big1) {
big2 = big1;
ibig2 = ibig1;
big1 = bgst[u.x] + u.y;
ibig1 = u.x;
} else if(bgst[u.x] + u.y > big2) {
big2 = bgst[u.x] + u.y;
ibig2 = u.x;
}
}
}
bgst[x] = big1;
ibgst[x] = ibig1;
//ibgst2[x] = ibig2;
if(big1 + big2 > now) {
now = big1 + big2;
inow = x;
}
}
void dfs2(int x) {
if(max(bgst[x], now - bgst[x]) < ansnow) {
ansnow = max(bgst[x], now - bgst[x]);
iansnow = x;
}
if(ibgst[x] != -1)
dfs2(ibgst[x]);
}
vector<int> points;
int best = -1, ibest;
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
int i, j;
for(i = 0; i < m; i ++) {
v[a[i]].pb({b[i], t[i]});
v[b[i]].pb({a[i], t[i]});
}
for(i = 0; i < n; i ++) {
if(done[i] == false) {
done[i] = true;
now = -1;
dfs(i, -1);
//lft = bgst[inow];
//rgh = now - lft;
ansnow = bgst[inow];
iansnow = inow;
//cout << "now: " << now << ' ' << inow << " " << ansnow << ' ' << iansnow << '\n';
dfs2(ibgst[inow]);
//cout << "ansnow: " << ansnow << ' ' << iansnow << '\n';
points.pb(iansnow);
if(ansnow > best) {
best = ansnow;
ibest = iansnow;
}
}
}
//cout << "best, ibest: " << best << ' ' << ibest << '\n';
for(auto w : points) {
//cout << "point " << w << '\n';
if(w != ibest) {
v[ibest].pb({w, l});
v[w].pb({ibest, l});
}
}
for(i = 0; i < n; i ++) {
bgst[i] = ibgst[i] = 0;
//ibgst2[i] = 0;
}
now = -1;
dfs(0, -1);
return now;
}
int a[maxn], b[maxn], t[maxn];
int main() {
cout << "working\n";
freopen("dreaming.in", "r", stdin);
freopen("dreaming.out", "w", stdout);
//cout << "!";
int n, m, l, i;
cin >> n >> m >> l;
for(i = 0; i < m; i ++) {
cin >> a[i] >> b[i] >> t[i];
//cout << "pai? " << i << " " << a[i] << ' ' << b[i] << ' ' << t[i] << '\n';
}
//cout << "?";
//cout << '\n';
cout << travelTime(n, m, l, a, b, t) << '\n';
return 0;
}
/*
for(i = 0; i < n; i ++) {
cin >> a[i];
}
for(i = 0; i < n; i ++) {
cin >> b[i];
}
for(i = 0; i < n; i ++) {
cin >> t[i];
}
*/