| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 679197 | kusssso | Dreaming (IOI13_dreaming) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
// #include "dreaming.h"
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
#define fi first
#define se second
vector<int> Tree;
ll d[N];
bool used[N];
int pa[N];
vector<pair<int, int>> g[N];
void dfs (int u, int p) {
Tree.push_back(u);
used[u] = 1;
pa[u] = p;
for (auto& e : g[u]) {
int v = e.fi;
int w = e.se;
if (v != p) {
d[v] = d[u] + w;
dfs(v, u);
}
}
}
int travelTime (int n, int m, int l, int A[], int B[], int T[]) {
for (int i = 0; i < m; i++) {
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
}
int pre = -1;
for (int i = 0; i < n; i++) {
if (!used[i]) {
dfs(i, -1);
int v = i;
for (auto& j : Tree) if (d[j] > d[v]) {
v = j;
d[j] = pa[j] = 0;
}
Tree.clear();
dfs(v, -1);
for (auto &j : Tree) if (d[j] > d[v]) v = j;
int u = v;
int x = v;
while (u != -1) {
if (abs(d[u] - d[v] / 2) < abs(d[x] - d[v] / 2)) {
x = u;
}
u = pa[u];
}
if (pre != -1) {
g[pre].push_back({x, l});
g[x].push_back({pre, l});
}
pre = x;
for (auto &j : Tree) {
d[j] = pa[j] = 0;
}
Tree.clear();
}
}
dfs(0, -1);
int v = 0;
for (int i = 0; i < n; i++) if (d[i] > d[v]) v = i, d[i] = 0;
dfs(v, -1);
for (int i = 0; i < n; i++) if (d[i] > d[v]) v = i;
return d[v];
}
// signed main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0);
//
// cout << travelTime(12, 8, 2, {0,8,2,5,5,1,1,10}, {8,2,7,11,1,3,9,6}, {4,2,4,3,7,1,5,3});
//
// return 0;
// }