Submission #773761

#	Time	Username	Problem	Language	Result	Execution time	Memory
773761		danikoynov	Rail (IOI14_rail)	C++14	8 / 100	294 ms	98568 KiB

rail

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

using namespace std;

const int maxn = 5010;
int dist[maxn][maxn], used[maxn];
void findLocation(int N, int first, int location[], int stype[])
{
    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 ++)
        {
            dist[i][j] = dist[j][i] = getDistance(i, j);
        }

    int closest = -1;
    for (int i = 1; i < N; i ++)
    {
        if (closest == -1 || dist[0][closest] > dist[0][i])
            closest = i;
    }

    location[closest] = location[0] + dist[0][closest];
    stype[0] = 1;
    stype[closest] = 2;

    int left = 0, right = closest;
    used[left] = used[right] = 1;

    int cnt = 2;
    while(cnt < N)
    {
        int closest_left = -1;
        int closest_right = -1;

        for (int i = 0; i < N; i ++)
        {
            if (used[i])
                continue;

            if (closest_left == -1 ||
                    dist[left][closest_left] > dist[left][i])
                closest_left = i;

            if (closest_right == -1 ||
                    dist[right][closest_right] > dist[right][i])
                closest_right = i;
        }

        if (closest_left != closest_right)
        {
            used[closest_left] = used[closest_right] = 1;
            location[closest_left] = location[left] + dist[left][closest_left];
            location[closest_right] = location[right] - dist[right][closest_right];
            stype[closest_left] = 2;
            stype[closest_right] = 1;
            right = closest_left;
            left = closest_right;
            cnt = cnt + 2;
        }
        else
        {
            int vertex = closest_left;
            used[vertex] = 1;
            cnt ++;
            if (dist[left][vertex] < dist[right][vertex])
            {
                location[vertex] = location[left] + dist[left][vertex];
                stype[vertex] = 2;
                right = vertex;
            }
            else
            {
                location[vertex] = location[right] - dist[right][vertex];
                stype[vertex] = 1;
                left = vertex;
            }
        }
    }
}

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