Submission #65616

#	Time	Username	Problem	Language	Result	Execution time	Memory
65616		Kubalionzzale	Rail (IOI14_rail)	C++14	30 / 100	99 ms	21212 KiB

rail

#include "rail.h"

#include <iostream>
#include <algorithm>

int dist[5010][5010];
int min = 1e7, two;

void findLocation(int n, int first, int location[], int stype[])
{
    location[0] = first;
    stype[0] = 1;

    for (int i = 1; i < n; ++i)
    {
        dist[i][0] = getDistance(i, 0);
        dist[0][i] = getDistance(0, i);

        if (dist[i][0] == dist[0][i] && dist[i][0] < min)
        {
            min = dist[i][0];
            two = i;
        }
    }

    location[two] = first + min;
    stype[two] = 2;

    for (int j = 1; j < n; ++j)
    {
        if (j == two)
            continue;

        dist[two][j] = getDistance(j, two);

        if (dist[0][j] == dist[two][j])
        {
            location[j] = first + dist[0][j];
            stype[j] = 1;
        }
        else if (dist[0][j] < dist[two][j])
        {
            location[j] = first + dist[0][j];

            if (dist[0][j] == dist[j][0])
                stype[j] = 2;
            else
                stype[j] = 1;
        }
        else if (dist[two][j] < dist[0][j])
        {
            location[j] = location[two] - dist[two][j];

            if (dist[two][j] + dist[two][0] == dist[j][0])
                stype[j] = 1;
            else
                stype[j] = 2;
        }
    }
/*
    for (int i = 0; i < n; ++i)
    {
        std::cout << location[i] << " " << stype[i] << "\n";
    }*/
}

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