Submission #69143

#	Time	Username	Problem	Language	Result	Execution time	Memory
69143		KLPP	Rail (IOI14_rail)	C++14	30 / 100	638 ms	99372 KiB

rail

#include "rail.h"
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int dist[5000][5000];
int ans[5000][2];
int n;
int cmp(int i, int j){
	return dist[i][0]<dist[j][0];
}
void findLocation(int N, int first, int location[], int stype[])
{
	n=N;
	stype[0]=1;
	location[0]=first;
	for(int i=0;i<N;i++){dist[i][i]=0;
		for(int j=i+1;j<N;j++){
			dist[i][j]=getDistance(i,j);
			dist[j][i]=dist[i][j];
		}
	}
	vector<int> med[n];
	for(int i=1;i<N;i++){
		for(int j=1;j<N;j++){
			if(i!=j && dist[0][i]==dist[0][j]+dist[i][j]){
				med[i].push_back(j);
			}
		}
		sort(med[i].begin(),med[i].end());
		/*for(int j=0;j<med[i].size();j++)cout<<med[i][j]<<" ";
		cout<<endl;*/
	}
	for(int i=1;i<N;i++){
		if(med[i].size()==0){
			location[i]=dist[0][i]+location[0];
			stype[i]=2;
		}
	}
	for(int i=1;i<N;i++){
		if(med[i].size()==1){
			location[i]=location[med[i][0]]-dist[med[i][0]][i];
			stype[i]=1;
		}	
	}
	for(int i=1;i<N;i++){
		if(med[i].size()==2){
			location[i]=location[med[i][0]]+dist[med[i][0]][i];
			stype[i]=2;
		}	
	}
	//for(int i=0;i<N;i++)cout<<location[i]<<endl;
	/*int D=1;
	for(int i=1;i<N;i++){
		if(dist[0][i]<dist[0][D]){
			D=i;
		}
	}
	for(int i=1;i<N;i++){
		if(dist[0][i]==dist[0][D]+dist[D][i]){
			stype[i]=1;
			location[i]=first+dist[0][D]-dist[D][i];
		}else{
			stype[i]=2;
			location[i]=first+dist[0][i];
		}
	}
	stype[D]=2;
	location[D]=dist[0][D]+first;
	stype[0]=1;
	location[0]=first;*/
}

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