제출 #133661

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
133661		Utaha	경주 (Race) (IOI11_race)	C++14	100 / 100	1167 ms	96232 KiB

race

#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=200005;
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;

int ans=INF;
bool vis[maxn];
vector<pair<int,ll>> edge[maxn];
vector<int> cmp;
int par[maxn];
int sz[maxn];
ll dis[maxn];
int c[maxn];
int anc[maxn];

vector<pair<ll,int>> 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(pair<int,ll> 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(pair<int,ll> 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(pair<int,ll> v:edge[cur]) if(!vis[v.F]){
				vis[v.F]=1;
				cmp.pb(v.F);
				par[v.F]=cur;
				dis[v.F]=dis[cur]+v.S;
				c[v.F]=c[cur]+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(int i:cmp) vis[i]=0;
	for(pair<int,ll> 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(int i:cmp) cout<<dis[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;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57