| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 122627 | ekrem | 꿈 (IOI13_dreaming) | C++98 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "dreaming.h"
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define coc g[node][i].st
#define yol g[node][i].nd
#define inf 1000000000000000007
#define N 1000005
using namespace std;
typedef long long ll;
typedef pair < ll , ll > ii;
ll dp[N], u[N], k;
ii c[N];
ii mn, mx;
vector < ii > g[N];
void hazirla(ll node, ll par){
for(ll i = 0; i < g[node].size(); i++){
if(coc == par)
continue;
hazirla(coc, node);
dp[node] = max(dp[node], dp[coc] + yol);
}
}
void dfs(ll node, ll us){
u[node] = 1;
mn = min(mn, mp(max(us, dp[node]), node) );
multiset < ll > s;
s.insert(0);
for(ll i = 0; i < g[node].size(); i++){
if(u[coc])
continue;
s.insert(dp[coc] + yol);
}
for(ll i = 0; i < g[node].size(); i++){
if(u[coc])
continue;
s.erase(s.find(dp[coc] + yol));
dfs(coc, max(us + yol, *s.rbegin() + yol));
s.insert(dp[coc] + yol);
}
}
void bul(ll node, ll par, ll yoll){
mx = max(mx, mp(yoll, node));
for(ll i = 0; i < g[node].size(); i++)
if(coc != par)
bul(coc, node, yoll + yol);
}
ll travelTime(ll n, ll m, ll l, ll a[], ll b[], ll t[]) {
for(ll i = 0; i < m; i++){
a[i]++;b[i]++;
g[a[i]].pb(mp(b[i], t[i]));
g[b[i]].pb(mp(a[i], t[i]));
}
// multiset < ll > s;
for(ll i = 1; i <= n; i++)
if(!u[i]){
mn.st = inf;
hazirla(i, 0);
dfs(i, 0);
c[++k] = mn;
// cout << mn.st << " " << mn.nd << endl;
}
sort(c + 1, c + k + 1);
for(ll i = 1; i < k; i++){
g[c[i].nd].pb(mp(c[k].nd, l));
g[c[k].nd].pb(mp(c[i].nd, l));
// cout << "AMK" << k << "AMK" << endl;
}
mx = mp(-inf, 0);
bul(1, 0, 0);
ll git = mx.nd;
mx = mp(-inf, 0);
bul(git, 0, 0);
return mx.st;
// mn = inf;
// for(ll i = 1; i <= k; i++){
// s.erase(s.find(c[i]));
// mn = min(mn, c[i] + *s.rbegin() + l);
// s.insert(c[i]);
// }
return 0;
}