제출 #590903

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

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

int dis[5010][5010];
void findLocation(int n, int first, int loc[], int type[])
{
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            dis[i][j] = getDistance(i,j);
    loc[0]=first, type[0]=1;
    int num = 0, mn = 1000000;
    for(int i = 1; i < n; i++) 
        if(dis[0][i]<mn) mn=dis[0][i],num=i;
    loc[num] = loc[0]+mn, type[num]=2;
    for(int i = 1; i < n; i++)
        if(i!=num) type[i]=(dis[0][i]==dis[0][num]+dis[num][i])?1:2;
    for(int i = 1; i < n; i++)
        if(type[i]==2) loc[i] = loc[0]+dis[0][i];
    for(int i = 1; i < n; i++)
        if(type[i]==1) loc[i] = loc[0]-(dis[0][i]-dis[0][num]*2);
}

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