Submission #50250

#	Time	Username	Problem	Language	Result	Execution time	Memory
50250		antimirage	Rail (IOI14_rail)	C++17	30 / 100	638 ms	118464 KiB

rail

#include "rail.h"

#include <bits/stdc++.h>

#define pb push_back
#define mk make_pair
#define fr first
#define sc second

using namespace std;

const int N = 6000;

int ar[N][N], in[N];

vector < pair <int, int> > vec;

void findLocation(int n, int First, int ans[], int type[])
{
int cnt = 0;

    type[0] = 1;
    ans[0] = First;

    if (n == 1)
        return;

    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            cnt++;
            ar[i][j] = getDistance(i, j);
            ar[j][i] = ar[i][j];
        }
    }
    assert(cnt == n * (n - 1) / 2);

    in[0] = 1;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i == j) continue;

            if ( ar[i][in[i]] > ar[i][j] )
                in[i] = j;
        }
    }

    type[ in[0] ] = 2;
    ans[ in[0] ] = ans[0] + ar[0][ in[0] ];

    for (int i = 0; i < n; i++)
        vec.pb( mk(i, in[i]) );

    for (auto it : vec)
    {
        if (type[it.fr] && type[it.sc])
            continue;

        if (type[it.fr] == 1)
        {
            type[it.sc] = 2;
            ans[it.sc] = ans[it.fr] + ar[it.fr][it.sc];
            continue;
        }
        if(type[it.sc] == 1)
        {
            type[it.fr] = 2;
            ans[it.fr] = ans[it.sc] + ar[it.fr][it.sc];
            continue;
        }
        if (type[it.fr] == 2)
        {
            type[it.sc] = 1;
            ans[it.sc] = ans[it.fr] - ar[it.fr][it.sc];
            continue;
        }
        if (type[it.sc] == 2)
        {
            type[it.fr] = 1 ;
            ans[it.fr] = ans[it.sc] - ar[it.fr][it.sc];
            continue;
        }
        if ( ar[0][it.fr] > ar[0][it.sc] ) swap(it.fr, it.sc);

        if (ar[0][it.fr] < ar[in[0]][it.fr])
        {
            type[ it.fr ] = 2;
            ans[ it.fr ] = ans[0] + ar[0][it.fr];

            type[it.sc] = 1;
            ans[ it.sc ] = ans[ it.fr ] - ar[it.fr][it.sc];
        }
        else
        {
            type[ it.fr ] = 1;
            ans[ it.fr ] = ans[in[0]] - ar[it.fr][in[0]];

            type[it.sc] = 2;
            ans[ it.sc ] = ans[ it.fr ] + ar[it.fr][it.sc];
        }
    }
}

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