| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 753962 | phoenix0423 | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
ll n, k, ans = 1e9;
vector<pll> adj[maxn];
ll w[maxn], vis[maxn], siz[maxn], h[maxn][2];
map<ll, ll> 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, ll dis, ll cnt){
if(tmp.find(dis) != tmp.end()) tmp[dis] = min(tmp[dis], cnt);
else tmp[dis] = cnt;
for(auto [x, idx] : adj[pos]){
if(x == prev || vis[x]) continue;
dfsans(x, pos, dis + w[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, w[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);
}
}
ll best_path(int n, int k, ll h[][2], ll w[]){
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);
}
centroid_decomposition(0);
return ans;
}
void read_input(){
cin>>n>>k;
for(int i = 0; i < n - 1; i++){
int a, b;
cin>>a>>b;
adj[a].eb(b, i);
adj[b].eb(a, i);
}
for(int i = 0; i < n - 1; i++) cin>>w[i];
}
int main(void){
ios::sync_with_stdio(false);
cin.tie(0);
read_input();
centroid_decomposition(0);
ll ans = best_path(n, k, h, w);
cout<<(ans > 1e7 ? -1 : ans)<<"\n";
}