Submission #773824

#	Time	Username	Problem	Language	Result	Execution time	Memory
773824		danikoynov	철로 (IOI14_rail)	C++14	30 / 100	323 ms	199632 KiB

rail

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

using namespace std;

const int maxn = 5010;
int dist[maxn][maxn], used[maxn];

int lf, rf, ftype[maxn], loc[maxn];
    int n;
void extend_rf(int to)
{
    used[to] = 1;
    ftype[to] = 2;
    loc[to] = loc[lf] + dist[lf][to];
    for (int i = 0; i < n; i ++)
    {
        if (used[i])
            continue;
        if (dist[to][i] < dist[to][lf])
        {
            ftype[i] = 1;
            used[i] = 1;
            loc[i] = loc[to] - dist[to][i];
        }
    }
    rf = to;
}

void extend_lf(int to)
{
    used[to] = 1;
    ftype[to] = 1;
    loc[to] = loc[rf] - dist[rf][to];
    for (int i = 0; i < n; i ++)
    {
        if (used[i])
            continue;
        if (dist[to][i] < dist[to][rf])
        {
            ftype[i] = 2;
            used[i] = 1;
            loc[i] = loc[to] + dist[to][i];
        }
    }
    lf = to;
}

void findLocation(int N, int first, int location[], int stype[])
{
    n = N;
    loc[0] = first;
    ftype[0] = 1;
    used[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;
    }


    lf = 0;
    rf = 0;
    extend_rf(closest);

    int last = 0;
    while(true)
    {
        /**int cnt = 0;
        for (int i = 0; i < N; i ++)
            cnt += used[i];
        assert(cnt != last);
        last = cnt;*/

        bool done = true;
        for (int i = 0; i < N; i ++)
            if (!used[i])
            {
                done = false;
                break;
            }

        if (done)
            break;

        int closest_lf = -1;

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

            if (closest_lf == -1 ||
                    dist[lf][closest_lf] > dist[lf][i])
                closest_lf = i;

            ///if (closest_rf == -1 ||
              ///      dist[rf][closest_rf] > dist[rf][i])
               // closest_rf = i;
        }

        int ft = -1;
        for (int i = 0; i < N; i ++)
        {
            if (!used[i] || ftype[i] == 1)
                continue;
            if (ft == - 1 || loc[i] < loc[ft])
                ft = i;
        }

        int lf_loc = loc[lf] - (dist[lf][closest_lf] - 2 * dist[lf][ft]);
        int rf_loc = loc[lf] + dist[lf][closest_lf];

        int df = -1;
        for (int i = 0; i < N; i ++)
        {
            if (!used[i] || ftype[i] == 2)
            continue;
            if (df == -1 || loc[i] > loc[df])
                df = i;
        }

        int st_loc = loc[rf] - dist[rf][closest_lf];
        int pt_loc = loc[rf] + (dist[rf][closest_lf] - 2 * dist[rf][df]);

        if (st_loc == lf_loc)
            extend_lf(closest_lf);
        else
        if (rf_loc == pt_loc)
            extend_rf(closest_lf);
        else
        {
            assert(1 == 0);
        }
    }

    for (int i = 0; i < N; i ++)
        stype[i] = ftype[i];

    for (int i = 0; i < N; i ++)
        location[i] = loc[i];

    ///for (int i = 0; i < N; i ++)
       /// cout << location[i] << endl;
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:77:9: warning: unused variable 'last' [-Wunused-variable]
   77 |     int last = 0;
      |         ^~~~

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