| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 782522 | phoenix0423 | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//centroid decomposition
//Submission : https://dmoj.ca/submission/5575237
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define pb push_back
#define eb emplace_back
#define f first
#define s second
const int maxn = 2e5 + 5;
int n, k, ans = 1e9;
vector<pll> adj[maxn];
int L[maxn], vis[maxn], siz[maxn], H[maxn][2];
map<int, int> all, tmp;
// find centroid, calculate answer for centroid, remove the node and recurse for further centroids
void dfssz(int pos, int prev){
siz[pos] = 1;
for(auto [x, idx] : adj[pos]){
if(x == prev || vis[x]) continue;
dfssz(x, pos);
siz[pos] += siz[x];
}
}
void dfsans(int pos, int prev, int dis, int cnt){
if(dis > k) return;
if(tmp.find(dis) != tmp.end()) tmp[dis] = min(tmp[dis], cnt);
else tmp[dis] = cnt;
if(all.find(k - dis) != all.end()) ans = min(ans, cnt + all[k - dis]);
for(auto [x, idx] : adj[pos]){
if(x == prev || vis[x]) continue;
dfsans(x, pos, dis + L[idx], cnt + 1);
}
}
int get_centroid(int pos, int prev, int sz){
for(auto [x, idx] : adj[pos]){
if(x != prev && !vis[x] && siz[x] > sz / 2) return get_centroid(x, pos, sz);
}
return pos;
}
void centroid_decomposition(int pos){
dfssz(pos, -1);
int centroid = get_centroid(pos, -1, siz[pos]);
vis[centroid] = 1;
all.clear();
all[0] = 0;
for(auto [x, idx] : adj[centroid]){
tmp.clear();
if(vis[x]) continue;
dfsans(x, -1, L[idx], 1);
for(auto [dis, cnt] : tmp){
if(all.find(k - dis) != all.end()) {
ans = min(ans, cnt + all[k - dis]);
}
}
for(auto [dis, cnt] : tmp){
if(all.find(dis) != all.end()) all[dis] = min(all[dis], cnt);
else all[dis] = cnt;
}
}
for(auto [x, idx] : adj[centroid]){
if(vis[x]) continue;
centroid_decomposition(x);
}
}
int best_path(int N, int K, int H[][], int l[]){
n = N, k = K;
for(int i = 0; i < n - 1; i++){
adj[H[i][0]].eb(H[i][1], i);
adj[H[i][1]].eb(H[i][0], i);
}
for(int i = 0; i < n - 1; i++) L[i] = l[i];
centroid_decomposition(0);
return (ans < 1e9 ? ans : -1);
}