Submission #293339

#	Time	Username	Problem	Language	Result	Execution time	Memory
293339		ant101	Rail (IOI14_rail)	C++14	30 / 100	444 ms	98820 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x.size())
#define pb push_back
#define fi first
#define se second
const int INF = (int)(1e9);
typedef pair<int,int> ii;
 
int dist[5005][5005];
int d(int a,int b){
	if(dist[a][b]!=-1)return dist[a][b];
	return dist[a][b]=dist[b][a]=getDistance(a,b);
}
int flip(int x){
	if(x==1)return 2;
	return 1;
}
int pivot;
bool compare(ii a,ii b){
	if(d(a.se,pivot)<d(b.se,pivot))return 1;
	else if(d(a.se,pivot)>d(b.se,pivot))return 0;
	return a.se<b.se;
}
 
void findLocation(int N, int first, int location[], int stype[])
{	
	memset(dist,-1,sizeof dist);
	for (int i = 0; i < N; ++i)
		stype[i]=0;
	location[0]=first;
	stype[0]=1;
	if(N==1)return;
	int x=-1,D=INF;
	for (int i = 1; i < N; ++i)
	{
		if(d(0,i)<D)
			x=i,D=d(0,i);
	}
	location[x]=first+D,stype[x]=2;
	vector<ii> R,L,M;
	for (int y = 1; y < N; ++y)
	{
		if(y==x)continue;
		if((d(x,y)+d(0,x)) == d(0,y))L.pb({d(x,y),y});
		else if(d(x,y)<d(x,0))M.pb({d(x,y),y});
		else R.pb({d(0,y),y});
	}
	sort(R.begin(),R.end());
	sort(L.begin(),L.end());
	sort(M.begin(),M.end());
	if(sz(R)){
		//int a=x;
		/*stype[a]=2;
		location[a]=location[0]+R[0].fi;*/
		vector<int> h={x};
		for (int i = 0; i < sz(R); ++i)
		{
			//cerr<<d(0,R[i].se)-d(0,a)-d(R[i].se,a)<<"\n";
			//pivot=R[i].se;
			//sort(R.begin()+i,R.end(),compare);
			for(auto a:h){
				//cerr<<a<<"\n";
				if(d(0,R[i].se)==(d(R[i].se,a)+d(0,a))){
					location[R[i].se]=location[a]-d(R[i].se,a),stype[R[i].se]=1;
				}
			}
			if(!stype[R[i].se])location[R[i].se]=location[0]+d(0,R[i].se),stype[R[i].se]=2,h.pb(R[i].se);
		}
	}
	if(sz(L)){
		//int a=0;
		/*for(auto it:L)
			cerr<<it.se<<" ";
		cerr<<"L ended ***********\n";*/
		/*stype[a]=1;
		location[a]=location[x]-L[0].fi;*/
		vector<int> h={0};
		for (int i = 0; i < sz(L); ++i)
		{
			//pivot=L[i].se;
			//sort(L.begin()+i,L.end(),compare);
			for(auto a:h)
				if(d(x,L[i].se)==(d(L[i].se,a)+d(x,a)))location[L[i].se]=location[a]+d(L[i].se,a),stype[L[i].se]=2;
			if(!stype[L[i].se])location[L[i].se]=location[x]-d(x,L[i].se),stype[L[i].se]=1,h.pb(L[i].se);
			//cout<<stype[L[i].se]<<" "<<location[L[i].se]<<"\n";
		}
	}
	//cerr<<"-------\n";
	for(auto it:M){
		stype[it.se]=1;
		location[it.se]=location[x]-it.fi;
	}
	/*for (int i = 0; i < N; ++i)
	{
		//assert(stype[i]!=-1);
		//cout<<stype[i]<<" "<<location[i]<<"\n";
	}*/
	//cerr<<"\n";//
}

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44