| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 468157 | SirCovidThe19th | Dreaming (IOI13_dreaming) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define pii pair<int, int>
#define f first
#define s second
const int mx = 1e5 + 5, inf = 1e9;
vector<pair<int, int>> adj[mx]; pii in[mx]; bool vis[mx];
void comb(pii &p, int x){
if (x > p.f) p.s = p.f, p.f = x;
else if (x > p.s) p.s = x;
}
void dfs1(int i, int p){
vis[i] = 1;
for (auto [x, w] : adj[i]) if (x != p){
dfs1(x, i);
comb(in[i], in[x].f + w);
}
}
void dfs2(int i, int p, int pout, int &mnD){
mnD = min(mnD, max(pout, in[i].f)); lg = max(lg, in[i].f + pout);
for (auto [x, w] : adj[i]) if (x != p){
int sib = (in[i].f == in[x].f + w) ? in[i].s : in[i].f;
int out = max(sib, pout) + w;
dfs2(x, i, out, mnD);
}
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]){
for (int i = 0; i < m; i++){
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
int w[3] = {-l, -l, -l};
for (int i = 0; i < n; i++) if (!vis[i]){
int mnD = 1e9; dfs1(i, 0); dfs2(i, 0, 0, mnD);
if (mnD > w[0]) w[2] = w[1], w[1] = w[0], w[0] = mnD;
else if (mnD > w[1]) w[2] = w[1], w[1] = mnD;
else if (mnD > w[2]) w[2] = mnD;
}
if (n == 1) return 0;
if (n == 2) return m ? T[0] : l;
return max({w[0] + w[1] + l, w[1] + w[2] + 2 * l, lg});
}