Submission #1013988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013988		amirhoseinfar1385	Rail (IOI14_rail)	C++17	30 / 100	257 ms	98644 KiB

rail

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

void findLocation(int N, int first, int location[], int stype[])
{
	n=N;
	location[0]=first;
	stype[0]=1;
	if(n==1){
		return ;
	}
	for(int i=0;i<n;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());
	for(int i=1;i<n;i++){
		int mn=1e7,wh=-1;
		int u1=v[i].second;
		for(int j=i-1;j>=0;j--){
			if(all[u1][v[j].second]<mn){
				mn=all[u1][v[j].second];
				wh=j;
			}
		}
		int u2=v[wh].second;
		stype[u1]=1+(stype[u2]==1);
	//	cout<<u1<<" "<<u2<<endl;
		if(stype[u1]==1){
			location[u1]=location[u2]-all[u1][u2];
		}else{
			location[u1]=location[u2]+all[u1][u2];
		}
	}
}

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