| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 865973 | yeediot | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
//Don't open the standings during contests.
const int mxn=2e5+5;
vector<pii>adj[mxn];
int cnt[mxn];
bool vis[mxn];
void cnt_sz(int v,int pa){
cnt[v]=1;
for(auto [u,d]:adj[v]){
if(vis[u] or u==pa)continue;
cnt_sz(u,v);
cnt[v]+=cnt[u];
}
}
int find(int v,int pa,int tar){
for(auto [u,d]:adj[v]){
if(vis[u] or u==pa)continue;
if(cnt[u]*2>tar)return find(u,v,tar);
}
return v;
}
int ans=8e10;
vector<pii>dis;
void dfs(int v,int pa,int l,int len,int k){
//cout<<v<<' '<<l<<' '<<len<<'\n';
if(l>k)return;
dis.pb({l,len});
for(auto [u,d]:adj[v]){
if(vis[u] or u==pa)continue;
dfs(u,v,l+1,len+d,k);
}
}
int f[mxn];
void cd(int v,int k,int n){
cnt_sz(v,v);
v=find(v,v,cnt[v]);
vis[v]=1;
vector<int>undo;
for(auto [u,d]:adj[v]){
if(vis[u])continue;
dis.clear();
dis.pb({0,0});
dfs(u,v,1,d,k);
for(int j=0;j<sz(dis);j++){
chmin(ans,f[k-dis[j].S]+dis[j].F);
// cout<<u<<' '<<dis[j].S<<' '<<dis[j].F<<' '<<f[k-dis[j].S]<<' '<<ans<<'\n';
}
for(int j=0;j<sz(dis);j++){
undo.pb(dis[j].S);
chmin(f[dis[j].S],dis[j].F);
}
}
for(auto x:undo)f[x]=8e10;
for(auto [u,d]:adj[v]){
if(vis[u])continue;
cd(u,k,n);
}
}
int best_path(int n,int k,int h[][2],int l[]){
for(int i=0;i<n-1;i++){
adj[h[i][0]].pb({h[i][1],l[i]});
adj[h[i][1]].pb({h[i][0],l[i]});
}
for(int i=0;i<=k;i++){
f[i]=8e10;
}
cd(0,k,n);
return (ans==8e10?-1:ans);
}
/*
input:
11 12
0 1
0 2
2 3
3 4
4 5
0 6
6 7
6 8
8 9
8 10
3
4
5
4
6
3
2
5
6
7
*/