| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 963917 | zNatsumi | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 2e5 + 5, oo = 1e14;
int n, k;
vector<ii> g[N];
namespace sub12{
int up[N][20], cnt[N], path[N], res = oo;
int timer, in[N], out[N];
void dfs(int u){
in[u] = ++timer;
for(int i = 1; i < 20; i++)
up[u][i] = up[up[u][i-1]][i-1];
for(auto x : g[u]){
int v = x.fi, w = x.se;
if(v == up[u][0]) continue;
up[v][0] = u;
cnt[v] = cnt[u] + 1;
path[v] = path[u] + w;
dfs(v);
}
out[u] = ++timer;
}
bool anc(int u, int v){
return in[u] <= in[v] && out[v] <= out[u];
}
int lca(int u, int v){
if(anc(u, v)) return u;
if(anc(v, u)) return v;
for(int i = 19; i >= 0; i--)
if(!anc(up[u][i], v)) u = up[u][i];
return up[u][0];
}
int dist(int u, int v){
return path[u] + path[v] - 2*path[lca(u, v)];
}
int cal(int u, int v){
return cnt[u] + cnt[v] - 2*cnt[lca(u, v)];
}
int solve(){
dfs(0);
int res = oo;
for(int u = 0; u < n; u++)
for(int v = u+1; v < n; v++)
if(dist(u, v) == k){
res = min(res, cal(u, v));
}
return (res == oo ? -1 : res);
}
}
namespace sub34{
const int V = 1e6 + 5;
int child[N], res = oo;
bool del[N];
map<int, int> path;
int cnt_child(int u, int p){
child[u] = 1;
for(auto x : g[u]){
int v = x.fi;
if(v == p || del[v]) continue;
child[u] += cnt_child(v, u);
}
return child[u];
}
int centroid(int u, int p, int sz){
for(auto x : g[u]){
int v = x.fi;
if(v == p || del[v]) continue;
if(child[v] > sz/2) return centroid(v, u, sz);
}
return u;
}
void cal(int u, int p, int cnt, int len){
if(len > k) return;
if(path.find(k - len) != path.end()) res = min(res, cnt + path[k - len]);
for(auto x : g[u]){
int v = x.fi, w = x.se;
if(v == p || del[v]) continue;
cal(v, u, cnt + 1, len + w);
}
return;
}
void upd(int u, int p, int cnt, int len){
if(len > k) return;
if(path.find(len) == path.end()) path[len] = cnt;
else path[len] = min(path[len], cnt);
for(auto x : g[u]){
int v = x.fi, w = x.se;
if(v == p || del[v]) continue;
upd(v, u, cnt + 1, len + w);
}
}
void dfs(int u){
int sz = cnt_child(u, u);
u = centroid(u, u, sz);
del[u] = true;
path.clear();
path[0] = 0;
for(auto x : g[u]){
int v = x.fi, w = x.se;
if(del[v]) continue;
cal(v, u, 1, w);
upd(v, u, 1, w);
}
for(auto x : g[u]){
int v = x.fi;
if(del[v]) continue;
dfs(v);
}
return;
}
int solve(){
dfs(0);
return (res == oo ? -1 : res);
}
}
int best_path(int _n, int _k, int h[][2], int l[]){
n = _n;
k = _k;
for(int i = 0; i < n-1; i++){
int u = h[i][0], v = h[i][1], w = l[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
if(n <= 1000) sub12::solve();
else sub34::solve();
}