이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include<bits/stdc++.h>
using namespace std;
///Subtask 3
///DFS with buckets
typedef long long ll;
struct edge
{
int to;
ll w;
};
vector<edge> adjList[200005];
int k;
int minimum=INT_MAX;
void dfs_sub2(int u,int p,int depth,ll path)
{
if(path==k) minimum=min(minimum,depth);
for(edge e: adjList[u]){
int v=e.to;
ll w=e.w;
if(p==v) continue;
dfs_sub2(v,u,depth+1,path+w);
}
}
ll parent_way[200005];
void fillParent(int u,int p)
{
for(edge e: adjList[u]){
int v=e.to;
ll w=e.w;
if(v==p) continue;
parent_way[v]=w;
fillParent(v,u);
}
}
vector<int>* bucket[200005];
void dfs(int u,int p)
{
int leaf=1;
for(edge e: adjList[u]){
int v=e.to;
ll w=e.w;
if(p==v) continue;
leaf=0;
dfs(v,u);
}
bucket[u]=new vector<int>(101);
for(edge e: adjList[u]){
int v=e.to;
ll w=e.w;
if(p==v) continue;
for(int i=1;i<k;i++){
int path_child=(*bucket[v])[i];
int path=(*bucket[u])[k-i];
if(path_child==0) continue;
if(path!=0)
minimum=min(minimum,path_child+path);
if((*bucket[u])[i]==0)
(*bucket[u])[i]=path_child;
else
(*bucket[u])[i]=min((*bucket[u])[i],path_child);
}
}
if(leaf) (*bucket[u])[ parent_way[u] ]=1;
if((*bucket[u])[k]!=0)
minimum=min(minimum,(*bucket[u])[k]);
if(!leaf){
for(int i=k;i>=1;i--){
if(i+parent_way[u]>k) continue;
int dist=i+parent_way[u];
if((*bucket[u])[i]!=0){
(*bucket[u])[dist]=(*bucket[u])[i]+1;
if(dist==k) minimum=min(minimum,(*bucket[u])[i]+1);
if(dist!=i) (*bucket[u])[i]=0;
}
}
}
}
int best_path(int n, int K, int H[][2], int L[])
{
k=K;
for(int i=0;i<n-1;i++){
int a=H[i][0];
int b=H[i][1];
ll w=L[i];
adjList[a].push_back({b,w});
adjList[b].push_back({a,w});
}
if(n<=1000){
for(int u=0;u<n;u++){
dfs_sub2(u,-1,0,0);
}
return (minimum!=INT_MAX)? minimum : -1;
}
fillParent(0,-1);
dfs(0,-1);
/*for(int i=0;i<n;i++){
cout<<i<<":";
for(int j=1;j<=k;j++){
if((*bucket[i])[j]!=0) cout<<j<<" "<<(*bucket[i])[j]<<endl;
}
cout<<endl;
}*/
return (minimum!=INT_MAX)? minimum : -1;
}
컴파일 시 표준 에러 (stderr) 메시지
race.cpp: In function 'void dfs(int, int)':
race.cpp:42:12: warning: unused variable 'w' [-Wunused-variable]
ll w=e.w;
^
race.cpp:50:12: warning: unused variable 'w' [-Wunused-variable]
ll w=e.w;
^
# | 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... |