Submission #1014112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014112		amirhoseinfar1385	Rail (IOI14_rail)	C++17	100 / 100	89 ms	63316 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=5000+10;
int n,all[maxn][maxn],vis[maxn][maxn];
map<int,int>mp;

void findLocation(int N, int first, int location[], int stype[])
{
	n=N;
	location[0]=first;
	stype[0]=1;
	mp[first]=0;
	if(n==1){
		return ;
	}
	for(int i=0;i<1;i++){
		for(int j=i+1;j<n;j++){
			all[i][j]=all[j][i]=getDistance(i,j);
		}
	}
	vector<pair<int,int>>v;
	for(int i=0;i<n;i++){
		v.push_back(make_pair(all[0][i],i));
	}
	sort(v.begin(),v.end());
	stype[v[1].second]=2;
	location[v[1].second]=first+all[0][v[1].second];
	mp[location[v[1].second]]=v[1].second;
	int l=0;
	int r=v[1].second;
	for(int i=2;i<n;i++){
		int u=v[i].second;
		int whl=0;
		if(u!=v[1].second&&all[u][v[1].second]==0){
			all[u][v[1].second]=all[v[1].second][u]=getDistance(u,v[1].second);
		}
		if(all[u][v[1].second]+all[v[1].second][0]==all[u][0]&&all[u][0]>2*all[0][v[1].second]){
			if(u!=l&&all[u][l]==0){
				all[u][l]=all[l][u]=getDistance(u,l);
			}
			if(l==0){
				if(all[u][v[1].second]+all[v[1].second][0]==all[u][0]&&all[u][0]>2*all[0][v[1].second]){
					whl=first-(all[u][0]-2*all[0][v[1].second]);
				}else{
					whl=first+10;
				}
			}else{
				whl=location[l]+(all[u][l]+all[l][0]-all[u][0])/2;
			}
			if(whl>first){
				whl=location[v[1].second]-all[u][v[1].second];
			}
			if(mp.count(whl)==0){
				stype[u]=1;
				location[u]=first+all[v[1].second][0]*2-all[u][0];
				mp[location[u]]=u;
				l=u;
				continue;
			}
			int z=mp[whl];
		//	if(u!=z&&all[u][z]==0){
		//		all[u][z]=all[z][u]=getDistance(u,z);
		//	}
			if(stype[z]==1&&abs(location[z]-location[l]+(all[u][0]-all[z][0]))==all[l][u]){
				stype[u]=2;
				location[u]=location[z]+(all[u][0]-all[z][0]);
				mp[location[u]]=u;
				continue;
			}else{
				stype[u]=1;
				location[u]=first+all[v[1].second][0]*2-all[u][0];
				mp[location[u]]=u;
				l=u;
				continue;
			}
		}else{
			if(u!=r&&all[u][r]==0){
				all[u][r]=all[r][u]=getDistance(u,r);
			}
			int whr=location[r]-(all[u][r]+all[r][0]-all[u][0])/2;
			if(mp.count(whr)==0||whr<=first){
				stype[u]=2;
				location[u]=first+all[u][0];
				mp[location[u]]=u;
				r=u;
				continue;
			}	
			int z=mp[whr];
		//	if(u!=z&&all[u][z]==0){
		//		all[u][z]=all[z][u]=getDistance(u,z);
		//	}
			if(stype[z]==2&&abs(location[r]-location[z]+(all[u][0]-all[z][0]))==all[r][u]){
				stype[u]=1;
				location[u]=location[z]-(all[u][0]-all[z][0]);
				mp[location[u]]=u;
				continue;
			}else{
				stype[u]=2;
				location[u]=first+all[u][0];
				mp[location[u]]=u;
				r=u;
				continue;

			}
		}
	}
}

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