| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1312344 | coderg | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include "bits/stdc++.h"
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define pb push_back
void setIO(string name = ""){if(name.size()){ freopen((name + ".in").c_str(), "r", stdin);freopen((name + ".out").c_str(), "w", stdout);}}
#define F(i,l,r) for(int i=(l);i<(r);++i)
#define FR(i,l,r) for(int i=(l);i>=(r);--i)
typedef long long ll;
const int maxn=1000005;
const int mod=1e9+7;
const int mox=2000*500+505;
const int inf=1e9;
int mnedges[maxn],ans,k;
struct Centroid{
int n;
vector<vector<pii> > adj;
vector<int> siz;
vector<bool> removed;
int cnt[20][2];
ll tot;
Centroid(int nodes,vector<int>& vals) : n(nodes), val(vals) {
adj.resize(n+1);
removed.assign(n,0);
siz.resize(n);
}
void add(int u,int v,int w){
adj[u].pb({v,w});
adj[v].pb({u,w});
}
void calcsiz(int u,int p){
siz[u]=1;
for(auto& e:adj[u]){
int v=e.fi;
if(v!=p && !removed[v]){
calcsiz(v,u);
siz[u]+=siz[v];
}
}
}
int findcentroid(int u,int p,int totnodes){
for(auto& e:adj[u]){
int v=e.fi;
if(v!=p && !removed[v] && siz[v]>totnodes/2)return findcentroid(v,u,totnodes);
}
return u;
}
vector<pii> pathnodes;
void getpathnodes(int u,int p,int curdist,int curedges){
if(curdist>k)return;
pathnodes.pb({curdist,curedges});
for(auto& e:adj[u]){
int v=e.fi,w=e.se;
if(v!=p && !removed[v])getpathnodes(v,u,curdist+w,curedges+1);
}
}
//this function changes for every problem
void descompose(int u){
calcsiz(u,-1);
int cen=findcentroid(u,-1,siz[u]);
mnedges[0]=0;
vector<int> modified;
modified.pb(0);
removed[cen]=1;
for(auto& e:adj[cen]){
int v=e.fi,w=e.se;
if(!removed[v]){
pathnodes.clear();
getpathnodes(v,cen,w,1);
for(auto& p:pathnodes){
int dist=p.fi,edges=p.se;
int target=k-dist;
if(target>=0 && mnedges[target]!=inf)ans=min(ans,edges+mnedges[target]);
}
for(auto& p:pathnodes){
int dist=p.fi,edges=p.se;
if(dist<=k){
if(mnedges[dist]==inf){
mnedges[dist]=edges;
modified.pb(dist);
}else{
mnedges[dist]=min(mnedges[dist],edges);
if(dist!=0)modified.pb(dist);
}
}
}
}
}
for(int idx:modified)mnedges[idx]=inf;
for(auto& e:adj[cen]){
int v=e.fi;
if(!removed[v])descompose(v);
}
}
};
int best_path(int N,int K,int H[][2],int L[]){
ans=inf;
k=K;
F(i,0,k+1)mnedges[i]=inf;
Centroid cd(N);
F(i,0,N-1)cd.add(H[i][0],H[i][1],L[i]);
cd.descompose(0);
if(ans==inf)return -1;
return ans;
}