제출 #295157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
295157		arayi	철로 (IOI14_rail)	C++17	56 / 100	419 ms	98808 KiB

rail

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

int n, fr, sm, sc;
int a[5010][5010];
int getmn(int aa)
{
    int mn = INT_MAX, ret = aa;
    for (int i = 0; i < n; i++)
    {
        if(aa == i) continue;
        if(a[aa][i] < mn) mn = a[aa][i], ret = i;
    }
    return ret;
}
void findLocation(int N, int first, int location[], int stype[])
{
    n = N;
    fr = first;
    for (int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; ++j) a[i][j] = a[j][i] = getDistance(i, j);
    }
    stype[0] = 1, location[0] = first;
    if(n == 1) return;
    sm = getmn(0), sc = a[0][sm] + fr;
    stype[sm] = 2, location[sm] = sc;
    for (int i = 1; i < n; i++)
    {
        if(i == sm) continue;
        int ss = getmn(i);
        if(ss == 0) stype[i] = 2, location[i] = fr + a[0][i];
        else if(ss == sm) stype[i] = 1, location[i] = sc - a[sm][i];
        else{
            if(a[0][sm] + a[sm][i] == a[0][i])
            {
                if(a[sm][ss] + a[ss][i] == a[sm][i]) stype[i] = 2, location[i] = sc - a[sm][ss] + a[ss][i];
                else stype[i] = 1, location[i] = sc - a[sm][i];
            }
            else
            {
                if(a[0][ss] + a[ss][i] == a[0][i]) stype[i] = 1, location[i] = fr + a[0][ss] - a[ss][i];
                else stype[i] = 2, location[i] = fr + a[0][i];
            }
        }
    }
    return;
}

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