Submission #133531

#	Time	Username	Problem	Language	Result	Execution time	Memory
133531		Utaha	Race (IOI11_race)	C++14	0 / 100	15 ms	13688 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<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)<<'\n';
// }

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