| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 279819 | shayan_p | 꿈 (IOI13_dreaming) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// And you curse yourself for things you never done
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
vector<pii> v[maxn];
int pr[maxn], prv[maxn], h[maxn];
bool mark[maxn];
int far(int u, int par = -1){
mark[u] = 1;
if(par == -1)
h[u] = 0;
int ans = u;
for(auto [y, c] : v[u]){
if(y != par){
h[y] = h[u] + c;
pr[y] = u;
prv[y] = c;
int x = far(y, u);
if(h[x] > h[ans])
ans = x;
}
}
return ans;
}
int travelTime(int n, int m, int L, int a[], int b[], int t[]){
for(int i = 0; i < m; i++){
v[a[i]].PB({b[i], t[i]});
v[b[i]].PB({a[i], t[i]});
}
int ans = 0;
vector<int> vec;
for(int i = 0; i < n; i++){
if(!mark[i]){
int A = far(i), B = far(A);
int tmp = B, tmpv = 0, LST = -1;
ans = max(ans, h[B]);
while(tmpv + tmpv < h[B]){
LST = prv[tmp];
tmpv+= prv[tmp];
tmp = pr[tmp];
}
tmpv = min(tmpv, h[B] - tmpv + LST);
vec.PB(tmpv);
}
}
if(sz(vec) == 1)
return ans;
if(sz(vec) == 2)
return max(ans, vec[0] + vec[1] + L);
sort(vec.begin(), vec.end());
int A = vec[sz(vec)-3], B = vec[sz(vec)-2], C = vec[sz(vec)-1];
return max({ans, L + B + C, L + L + A + B});
}