| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 133529 | Utaha | Race (IOI11_race) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
const ll maxn=1005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;
bool vis[maxn];
vector<pll> edge[maxn];
vector<int> cmp;
int par[maxn];
int sz[maxn];
ll dis[maxn];
int c[maxn];
int anc[maxn];
vector<pii> data[maxn];
int rec[1000005];
void CD(int u,int req){
cmp.clear();
cmp.pb(u);
vis[u]=1;
par[u]=-1;
{
int pt=0;
while(pt<SZ(cmp)){
int cur=cmp[pt++];
for(pll v:edge[cur]) if(!vis[v.F]){
vis[v.F]=1;
cmp.pb(v.F);
par[v.F]=cur;
}
}
}
for(int i:cmp) vis[i]=0;
reverse(ALL(cmp));
int centroid=-1;
for(int u:cmp){
sz[u]=1;
bool f=1;
for(pii v:edge[u]) if(!vis[v.F]&&v.F!=par[u]){
sz[u]+=sz[v.F];
if(sz[v.F]+sz[v.F]>SZ(cmp)) f=0;
}
if(sz[u]+sz[u]<SZ(cmp)) f=0;
if(f) centroid=u;
}
// for(int i:cmp) cout<<i<<' ';
// cout<<'\n';
// for(int i:cmp) cout<<sz[i]<<' ';
// cout<<'\n';
cmp.clear();
cmp.pb(centroid);
vis[centroid]=1;
par[centroid]=-1;
dis[centroid]=0;
c[centroid]=0;
{
int pt=0;
while(pt<SZ(cmp)){
int cur=cmp[pt++];
for(pll v:edge[cur]) if(!vis[v.F]){
vis[v.F]=1;
cmp.pb(v.F);
par[v.F]=v.S;
dis[v.F]=dis[u]+v.F;
c[v.F]=c[u]+1;
if(dis[v.F]==req) ans=min(ans,c[v.F]);
if(cur==centroid){
anc[v.F]=v.F;
data[v.F].clear();
}
else anc[v.F]=anc[cur];
data[anc[v.F]].pb(MP(dis[v.F],c[v.F]));
}
}
}
for(pll v:edge[centroid]) if(!vis[v.F]){
for(auto i:data[v.F]) if(i.F<=req){
if(rec[req-i.F]!=0){
ans=min(ans,rec[req-i.F]+i.S);
}
}
for(auto i:data[v.F]) if(i.F<=req){
rec[i.F]=(rec[i.F]==0)?i.S:min(rec[i.F],i.S);
}
}
for(int i:cmp) if(dis[i]<=req){
rec[dis[i]]=0;
}
for(int i:cmp) vis[i]=0;
vis[centroid]=1;
// cout<<"center: "<<centroid<<'\n';
// for(int i:cmp) cout<<i<<' ';
// cout<<'\n';
for(auto v:edge[centroid]) if(!vis[v.F]) CD(v.F,req);
}
int best_path(int n,int k,int e[][2],int l[]){
memset(rec,0,sizeof rec);
REP(i,n-1){
edge[e[i][0]].pb(MP(e[i][1],l[i]));
edge[e[i][1]].pb(MP(e[i][0],l[i]));
}
CD(0,k);
if(ans==INF) ans=-1;
return ans;
}
/*
int e[][2]={{0,1},{0,2},{2,3},{3,4},{4,5},{0,6},{6,7},{6,8},{8,9},{8,10}};
int l[]={3,4,5,4,6,3,2,5,6,7};
int main(){
cout<<best_path(11,12,e,l);
}
*/