제출 #1013968

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1013968		amirhoseinfar1385	철로 (IOI14_rail)	C++17	0 / 100	3093 ms	98572 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);
		}
	}
	int res1=0,res2=0;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			int z=0;
			for(int h=0;h<n;h++){
				if(h==i||h==j){
					continue;
				}
				if(all[i][j]==all[i][h]+all[h][j]){
					z=1;
				}
			}
			if(z==0){
				res1=i;
				res2=j;
			}
		}
	}
	int mn=1e7,wh=-1;
	for(int i=1;i<n;i++){
		if(mn>all[0][i]){
			wh=i;
			mn=all[0][i];
		}
	}
	if(all[res1][wh]+all[res2][wh]!=all[res1][res2]+all[0][wh]){
		swap(res1,res2);
	}
	stype[res1]=1;
	stype[res2]=2;
	//cout<<res1<<" wef "<<res2<<endl;
	location[res2]=first+all[0][res2];
	location[res1]=location[res2]-all[res2][res1];
	for(int i=0;i<n;i++){
		if(i==res1||i==res2||i==0){
			continue;
		}
		if(all[res2][0]+all[0][i]==all[res2][i]){
			stype[i]=2;
			location[i]=first+all[0][i];
		}else{
			stype[i]=1;
			location[i]=location[res2]-all[res2][i];
		}
	}
}

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