# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
344812 | Tosic | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
int n, k, ans, minSz, curCn, minDistance[10*maxn];
bool isC[maxn];
vector<vector<pair<int, int> > > gr;
vector<int> subSz;
int findCentroid(int x, int p, int dist, int price, int n){
subSz[x] = 1;
int tmpM = 0;
for(auto pr : gr[x]){
int i = pr.first,c = pr.second;
if(isC[i] or i == p){
continue;
}
subSz[x] += findCentroid(i, x, dist+1, price+c, n);
tmpM = max(subSz[i], tmpM);
}
tmpM = max(tmpM, n-subSz[x]);
if(minSz > tmpM){
minSz = tmpM;
curCn = x;
}
return subSz[x];
}
vector<int> chPrices;
void dfs(int x, int p, int dist, int price, bool isAdding){
if(price>maxn*10){
return;
}
if(isAdding and price < maxn*10){
minDistance[price] = min(minDistance[price],dist);
chPrices.push_back(price);
} else {
if(k - price >= 0){
ans = min(ans, dist + minDistance[k-price]);
}
}
for(auto tmp:gr[x]){
int i = tmp.first, j = tmp.second;
if(isC[i] or i ==p){
continue;
}
dfs(i, x, dist+1, price + j, isAdding);
}
}
void findR(int x, int n){
minSz = 1e9;
curCn = x;
findCentroid(x, -1, 0, 0, n);
isC[curCn] = 1;
for(auto tmp:gr[curCn]){
int i = tmp.first, j = tmp.second;
if(!isC[i]){
dfs(i, curCn, 1, j, 0);
dfs(i, curCn, 1, j, 1);
}
}
unique(chPrices.begin(), chPrices.end());
for(auto x : chPrices){
minDistance[x] = 1e9;
}
minDistance[0] = 0;
chPrices.clear();
for(auto tmp:gr[curCn]){
int i = tmp.first, j = tmp.second;
if(!isC[i]){
findR(i, subSz[i]);
}
}
}
void best_path(int n, int K, int h[][2], int l[]){
gr.resize(n, vector<pair<int, int> >());
k = K;
for(int i = 0; i < n-1; ++i){
int x, y, w;
x = h[i][0];
y = h[i][1];
w = l[i];
gr[x].push_back({y, w});
gr[y].push_back({x, w});
}
subSz.resize(n, 0);
for(int i = 1; i < maxn*10; ++i){
minDistance[i] = 1e9;
}
ans = 1e9;
findR(0, n);
if(ans != 1e9){
return ans;
} else {
return -1;
}
}