| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 229676 | DavidDamian | 경주 (Race) (IOI11_race) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "race.h"
#include<bits/stdc++.h>
using namespace std;
///Subtask 3
///DFS with buckets
typedef long long ll;
struct edge
{
ll to;
ll w;
};
vector<edge> adjList[200005];
ll k;
ll minimum=LLONG_MAX;
void dfs_sub2(ll u,ll p,ll depth,ll path)
{
if(path==k) minimum=min(minimum,depth);
for(edge e: adjList[u]){
ll 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(ll u,ll p)
{
for(edge e: adjList[u]){
ll v=e.to;
ll w=e.w;
if(v==p) continue;
parent_way[v]=w;
fillParent(v,u);
}
}
vector<ll>* bucket[200005];
void dfs(ll u,ll p)
{
ll leaf=1;
for(edge e: adjList[u]){
ll v=e.to;
ll w=e.w;
if(p==v) continue;
leaf=0;
dfs(v,u);
}
bucket[u]=new vector<ll>(101);
for(edge e: adjList[u]){
ll v=e.to;
ll w=e.w;
if(p==v) continue;
for(ll i=0;i<k;i++){
ll path_child=(*bucket[v])[i];
ll 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((*bucket[v])[k]!=0) minimum=min(minimum,(*bucket[v])[k]);
}
if(leaf) (*bucket[u])[ parent_way[u] ]=1;
if((*bucket[u])[k]!=0)
minimum=min(minimum,(*bucket[u])[k]);
if(!leaf){
for(ll i=k;i>=1;i--){
if((ll)i+parent_way[u]>k) continue;
ll dist=i+parent_way[u];
if((*bucket[u])[i]!=0){
(*bucket[u])[dist]=(*bucket[u])[i]+1;
if(dist!=i) (*bucket[u])[i]=0;
}
}
(*bucket[u])[ parent_way[u] ]=1;
}
}
int best_path(ll n, ll K, ll H[][2], ll L[])
{
k=K;
for(ll i=0;i<n-1;i++){
ll a=H[i][0];
ll b=H[i][1];
ll w=L[i];
adjList[a].push_back({b,w});
adjList[b].push_back({a,w});
}
if(n<=1000){
for(ll u=0;u<n;u++){
dfs_sub2(u,-1,0,0);
}
return (minimum!=LLONG_MAX)? minimum : -1;
}
fillParent(0,-1);
dfs(0,-1);
/*for(ll i=0;i<n;i++){
cout<<i<<":";
for(ll j=0;j<=k;j++){
if((*bucket[i])[j]!=0) cout<<j<<" "<<(*bucket[i])[j]<<endl;
}
cout<<endl;
}*/
return (minimum!=LLONG_MAX)? minimum : -1;
}