| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 372468 | two_sides | 꿈 (IOI13_dreaming) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector <pair <int, int>> adj[N];
int par[N], dis[N];
queue <int> que;
void BFS(int u, int &diam, int &dist) {
int far = u; diam = 0;
que.push(u); dis[u] = 0; par[u] = -1;
while (que.size()) {
u = que.front(); que.pop();
if (dis[u] > diam) {
diam = dis[u]; far = u;
}
for (auto e : adj[u]) {
int v, w; tie(v, w) = e;
if (v != par[u]) {
dis[v] = dis[u] + w;
par[v] = u; que.push(v);
}
}
}
que.push(u = far);
diam = dis[u] = 0; par[u] = -1;
while (que.size()) {
u = que.front(); que.pop();
if (dis[u] > diam) {
diam = dis[u]; far = u;
}
for (auto e : adj[u]) {
int v, w; tie(v, w) = e;
if (v != par[u]) {
dis[v] = dis[u] + w;
par[v] = u; que.push(v);
}
}
}
dist = INT_MAX; u = far;
while (u >= 0) {
dist = min(dist, max
(dis[u], dis[far] - dis[u]));
u = par[u];
}
}
int travelTime(int n, int m, int l,
vector <int> a, vector <int> b, vector <int> t) {
for (int i = 0; i < m; i++) {
adj[a[i]].emplace_back(b[i], t[i]);
adj[b[i]].emplace_back(a[i], t[i]);
}
memset(dis, -1, sizeof dis);
vector <int> tmp; int res = 0;
for (int i = 0; i < n; i++)
if (dis[i] < 0) {
int diam, dist;
BFS(i, diam, dist);
res = max(res, diam);
tmp.push_back(dist);
}
sort(tmp.begin(), tmp.end());
assert(tmp.size() == n - m);
for (int i = 0; i + 1 < n - m; i++)
tmp[i] += l;
sort(tmp.begin(), tmp.end());
if (n - m > 1)
res = max(res,
tmp[n - m - 1] + tmp[n - m - 2]);
return res;
}