제출 #550701

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
550701		CSQ31	철로 (IOI14_rail)	C++17	30 / 100	356 ms	98432 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
int d[5001][5001];
void findLocation(int n, int f, int location[], int stype[])
{
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			d[i][j] = d[j][i] = getDistance(i,j);
		}
	}
	location[0] = f;
	stype[0] = 1;
	vector<int>mn(n,0);
	for(int i=0;i<n;i++){
		int c = 1e9;
		for(int j=0;j<n;j++){
			if(i==j)continue;
			if(c > d[i][j]){
				c = d[i][j];
				mn[i] = j;
			}
		}
	}
	int x = mn[0];
	stype[x] = 2;
	location[x] = d[x][0];
	for(int i=1;i<n;i++){
		if(mn[i] == 0){
			stype[i] = 2;
			location[i] = f + d[0][i];
		}
	}
	int c = 1e9;
	for(int i=0;i<n;i++){
		if(stype[i] == 2){
			if(c > location[i]){
				c = location[i];
				x = i;
			}
		}
	}
	for(int i=0;i<n;i++){
		if(!stype[i]){
			stype[i] = 1;
			location[i] = c-d[i][x];
			
		}
	}
	//for(int i=0;i<n;i++)cout<<stype[i]<<" "<<location[i]<<'\n';
}

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