Submission #93851

#	Time	Username	Problem	Language	Result	Execution time	Memory
93851		Alexa2001	Rail (IOI14_rail)	C++17	30 / 100	819 ms	108332 KiB

rail

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

using namespace std;

const int Nmax = 5505;

int dist[Nmax][Nmax];
bool used[Nmax];

void findLocation(int N, int F, int location[], int stype[])
{
    int i, j, n = N;
    for(i=0; i<n; ++i)
    {
        dist[i][i] = 1e9;
        for(j=i+1; j<n; ++j)
            dist[i][j] = dist[j][i] = getDistance(i, j);
    }

    int X = 0, Y = 0;
    for(i=0; i<n; ++i)
        if(dist[0][i] < dist[0][Y]) Y = i;

    for(i=0; i<n; ++i)
        if(dist[Y][i] < dist[X][Y]) X = i;

    used[X] = used[Y] = 1;
    location[Y] = F + dist[0][Y];
    location[X] = location[Y] - dist[X][Y];
    stype[X] = 1; stype[Y] = 2;

    int lastst1, lastst2, lastdr1, lastdr2;

    lastdr1 = X; lastdr2 = Y;
    lastst1 = X; lastst2 = Y;

    for(i=0; i<n-2; ++i)
    {
        int k = -1;
        for(j=0; j<n; ++j)
            if(!used[j] && (dist[j][X] < dist[k][X] || k == -1)) k = j;

        used[k] = 1;

        if(dist[k][X] < dist[k][Y]) /// e in dreapta
        {
            if(dist[k][lastdr2] == dist[k][lastdr1] + dist[lastdr2][lastdr1]) /// e 2
            {
                location[k] = location[X] + dist[X][k];
                stype[k] = 2;
                if(location[k] > location[lastdr2]) lastdr2 = k;
            }
            else
            {
                stype[k] = 1;
                for(j=0; j<n; ++j)
                    if(used[j] && stype[j] == 2 && location[j] >= location[Y] && dist[k][X] == dist[k][j] + dist[j][X])
                        location[k] = location[j] - dist[j][k];
                if(location[k] > location[lastdr1]) lastdr1 = k;
            }
        }
        else /// e in stanga
        {
            if(dist[k][lastst1] == dist[k][lastst2] + dist[lastst1][lastst2]) /// e 1
            {
                location[k] = location[Y] - dist[Y][k];
                stype[k] = 1;
                if(location[k] < location[lastst1]) lastst1 = k;
            }
            else
            {
                stype[k] = 2;
                for(j=0; j<n; ++j)
                    if(used[j] && stype[j] == 1 && location[j] <= location[X] && dist[k][Y] == dist[k][j] + dist[j][Y])
                        location[k] = location[j] + dist[j][k];
                if(location[k] < location[lastst2]) lastst2 = k;
            }
        }
    }
}

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