| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 349798 | Pety | 꿈 (IOI13_dreaming) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int N = 1e5 + 2;
int up[N], k, down[N], bestTime[N];
bool viz[N];
vector<pair<int, int> > G[N];
void dfs (int nod, int p) {
for (auto it : G[nod])
if (it.first != p) {
dfs(it.first, nod);
down[nod] = max(down[nod], down[it.first] + it.second);
}
}
void dfs2 (int nod, int p) {
vector<int>pref;
vector<int>suf;
viz[nod] = 1;
for (auto it : G[nod])
if (it.first != p) {
up[it.first] = up[nod] + it.second;
pref.push_back(down[it.first] + it.second);
}
suf = pref;
for (int i = 1; i < pref.size(); i++)
pref[i] = max(pref[i - 1], pref[i]);
for (int i = suf.size() - 2; i >= 0; i--)
suf[i] = max(suf[i + 1], suf[i]);
int useless = 0;
for (auto it : G[nod])
if (it.first != p) {
int value = 0;
if (useless > 0)
value = pref[useless - 1];
if (useless < suf.size() - 1)
value = max(value, suf[useless + 1]);
up[it.first] = max(up[it.first], value + it.second);
useless++;
dfs2(it.first, nod);
}
bestTime[k] = min(bestTime[k], max(down[nod], up[nod]));
}
int timeTravel (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]});
}
for (int i = 1; i <= n; i++)
if (!viz[i]) {
k++;
bestTime[k] = 1e9 + 2;
dfs(i, 0);
dfs2(i, 0);
}
sort(bestTime + 1, bestTime + k + 1, greater<int>());
if (k == 1)
return bestTime[1];
if (k == 2)
return l + bestTime[1] + bestTime[2];
else
return max(l + bestTime[1] + bestTime[2], bestTime[2] + bestTime[3] + 2 * l);
}
int a[N], b[N], t[N], n, m, l;
/*int main ()
{
cin >> n >> m >> l;
for (int i = 1; i <= m; i++) {
cin >> a[i] >> b[i] >> t[i];
a[i]++; b[i]++;
}
cout << timeTravel(n, m, l, a, b, t);
return 0;
}*/
/**
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
**/