| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1154968 | bronze_coder | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
int best_path(int n,int k,vector<vector<int>> h,vector<int> l){
vector<vector<pair<int,int>>> adj(n);
for(int i=0;i<n-1;i++){
int a = h[i][0];
int b = h[i][1];
adj[a].push_back({b,l[i]});
adj[b].push_back({a,l[i]});
}
vector<int> q(1,0);
vector<int> parent(n,-1);
vector<int> dist(n,0);
vector<long long> len(n,0);
for(int i=0;i<n;i++){
int a = q[i];
for(auto j:adj[a]){
if(j.first!=parent[a]){
parent[j.first] = a;
q.push_back(j.first);
dist[j.first] = dist[a]+1;
len[j.first] = len[a]+j.second;
}
}
}
vector<map<long long,int>> v(n);
for(int i=0;i<n;i++){
v[i][len[i]] = dist[i];
}
int ans = n;
for(int j=n-1;j>0;j--){
int i = q[j];
int m = parent[i];
if(v[m].size()<v[i].size()){
swap(v[m],v[i]);
}
v[i][len[m]] = dist[m];
for(auto z:v[i]){
if(v[m].find(2*len[m]-z.first+k)!=v[m].end()){
ans = min(ans,v[m][2*len[m]-z.first+k]+z.second-2*dist[m]);
}
}
for(auto z:v[i]){
if(v[m][z.first]==0){
v[m][z.first] = v[i][z.first];
}
else{
v[m][z.first] = min(v[m][z.first],v[i][z.first]);
}
}
}
if(ans==n){
return -1;
}
return ans;
}