Submission #417565

#	Time	Username	Problem	Language	Result	Execution time	Memory
417565		benedict0724	Rail (IOI14_rail)	C++17	56 / 100	584 ms	98584 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

using namespace std;

int dist[5002][5002];

int span[5002];
bool U[5002];

void findLocation(int N, int first, int location[], int stype[])
{
    for(int i=0;i<N;i++)
    {
        for(int j=i+1;j<N;j++)
        {
            dist[i][j] = getDistance(i, j);
            dist[j][i] = dist[i][j];
        }
    }

    U[0] = 1;
    stype[0] = 1;
    location[0] = first;
    for(int i=1;i<N;i++) span[i] = 0;
    for(int i=1;i<N;i++)
    {
        int opt = -1;
        for(int j=0;j<N;j++)
        {
            if(U[j]) continue;
            if(opt == -1 || dist[span[opt]][opt] > dist[span[j]][j]) opt = j;
        }
        int pr = span[opt];
        U[opt] = true;
        stype[opt] = 3 - stype[pr];
        if(stype[pr] == 1) location[opt] = location[pr] + dist[opt][pr];
        else location[opt] = location[pr] - dist[opt][pr];

        for(int j=0;j<N;j++) if(dist[span[j]][j] > dist[opt][j]) span[j] = opt;
    }
}

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