# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
833061 | idiotcomputer | 경주 (Race) (IOI11_race) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2*1e5;
set<pair<long long int, int>> all[mxN];
int p[mxN];
long long int add[mxN];
int a2[mxN];
int res;
int k;
void upd(int c){
while (p[c] != p[p[c]]){
p[c] = p[p[c]];
}
}
void comb(int a, int b){
if (all[a].size() > all[b].size()){
swap(a,b);
}
for (auto it = all[a].begin(); it != all[a].end(); it++){
long long int val = (*it).first + add[a] - add[b];
int nl = (*it).second + a2[a] - a2[b];
long long int needed = k - val - 2*add[b];
auto it2 = all[b].lower_bound({needed,-1 * 1e9});
if (it2 != all[b].end() && (*it2).first == needed){
res = min(res, nl + (*it2).second + 2 * a2[b]);
}
all[b].insert({val,nl});
// cout << "HERERE " << a << " "<<b<< ": " << val+add[b] << " " << nl + a2[b] <<'\n';
}
p[a] = b;
}
void dfs(int node, int parent, vector<vector<pair<int,int>>> &connect){
p[node] = node;
add[node] = 0;
a2[node] = 0;
all[node].clear();
int next;
for (int i =0; i < connect[node].size(); i++){
next = connect[node][i].first;
if (next == parent){
continue;
}
dfs(next,node,connect);
upd(node);
upd(next);
int a= p[node];
int b = p[next];
add[b] += connect[node][i].second;
a2[b] += 1;
auto it = all[b].lower_bound({k-add[b],-1*1e9});
if (it != all[b].end() && (*it).first == k-add[b]){
res = min(res, (*it).second + a2[b]);
}
comb(a,b);
}
upd(node);
all[p[node]].insert({-1*add[p[node]],-1*a2[p[node]]});
/* cout<< node << ":\n";
for (auto it = all[p[node]].begin(); it != all[p[node]].end(); it++){
cout << (*it).first+add[p[node]] << "," << (*it).second+a2[p[node]] << ' ';
}
cout << '\n';*/
}
int best_path(int n,int ck, int h[][2], int l[]){
vector<vector<pair<int,int>>> connect(n);
k = ck;
for (int i =0; i < n-1; i++){
connect[h[i][0]].push_back({h[i][1],l[i]});
connect[h[i][1]].push_back({h[i][0],l[i]});
}
/* for (int i =0; i < n; i++){
cout << i << ": ";
for (int j = 0; j < connect[i].size();j++){
cout<<connect[i][j].first<<","<<connect[i][j].second<<" ";
}
cout<<'\n';
}*/
res = 1e9;
dfs(0,-1,connect);
if (res == 1e9){
return -1;
}
return res;
}
int main()
{
int h[mxN][2];
int l[mxN];
int n,ck;
cin >> n >> ck;
for (int i =0; i < n-1; i++){
cin >> h[i][0] >> h[i][1];
}
for (int i =0; i < n-1; i++){
cin >> l[i];
}
cout << best_path(n,ck,h,l);
return 0;
}