이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "race.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,fma,sse,sse2,sse4")
using namespace std;
typedef long long ll;
vector<pair<int,int>> adj[200001];
int sz[200001];
bool marked[200001]={0};
int m[1000001];
int k;
int dfs_sizes(int v, int pV){
sz[v]=0;
for(auto [w,d] : adj[v]){
if(w!=pV&&!marked[w]){
sz[v]+=dfs_sizes(w,v);
}
}
return sz[v];
}
int dfs_centroid(int v, int pV, int subtree_sz){
for(auto [w,d] : adj[v]){
if(pV!=w&&!marked[w]&&sz[w]>=(subtree_sz/2)){
return dfs_centroid(w,v,subtree_sz);
}
}
return v;
}
void dfs_paths(int v, int pV,int dist,int l, vector<pair<int,int>> &a){
for(auto [w,d] : adj[v]){
if(w!=pV&&!marked[w]){
if(dist+d<=k){
a.push_back({dist+d,l+1});
dfs_paths(w,v,dist+d,l+1,a);
}
}
}
}
int centroid_decomposition(int v){
int c = dfs_centroid(v,v,dfs_sizes(v,v));
marked[c]=1;
int ans=1000001;
vector<int> sus;
for(auto [w,d] : adj[c]){
if(!marked[w]){
vector<pair<int,int>> a;
dfs_paths(w,c,d,1,a);
for(auto [dist,l] : a){
if(m[k-dist]!=1000001){
ans=min(ans,l+m[k-dist]);
}
}
for(auto [dist,l] : a){
if(m[dist]!=1000001)m[dist]=min(m[dist],l);
else{
m[dist]=l;
sus.push_back(dist);
}
}
}
}
for(int i : sus)m[i]=1000001;
for(auto [w,d] : adj[c]){
if(!marked[w]){
ans = min(ans,centroid_decomposition(w));
}
}
return ans;
}
int best_path(int N, int K, int H[][2], int L[]){
for(ll i=0;i<N-1;i++){
adj[H[i][0]].push_back({H[i][1],L[i]});
adj[H[i][1]].push_back({H[i][0],L[i]});
}
k=K;
for(int i=0;i<=k;i++)m[i]=1000001;
m[0]=0;
ll ans = centroid_decomposition(0);
return (ans==1000001?-1:ans);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |