Submission #50238

#	Time	Username	Problem	Language	Result	Execution time	Memory
50238		antimirage	Rail (IOI14_rail)	C++17	30 / 100	594 ms	98736 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 = 5005;

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

vector < pair <int, int> > vec;

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

    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            ar[i][j] = getDistance(i, j);
            ar[j][i] = ar[i][j];
        }
    }
    for (int i = 0; i < n; i++)
    {
        in[i] = (i + 1) % n;
        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] ] = First + ar[0][ in[0] ];

    u[0] = u[ in[0] ] = 1;

    for (int i = 1; i < n; i++)
    {
        if (u[i]) continue;
        vec.pb( mk(i, in[i]) );
        u[i] = u[ in[i] ] = 1;
    }
    for (auto it : vec)
    {
        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 ] = First + 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 ] = First + ar[0][in[0]] - ar[it.fr][in[0]];

            type[it.sc] = 2;
            ans[ it.sc ] = ans[ it.fr ] + ar[it.fr][it.sc];
        }
    }
//    cout << endl;
//    for (int i = 0; i < n; i++)
//    {
//        cout <<type[i] << " " << ans[i] << endl;
//    }
}

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