Submission #371086

#	Time	Username	Problem	Language	Result	Execution time	Memory
371086		idk321	Rail (IOI14_rail)	C++11	56 / 100	1331 ms	98704 KiB

rail

#include "rail.h"

#include <bits/stdc++.h>
using namespace std;



const int N = 5005;
const int M = 1000005;
int dist[N][N];
int distNow[N];
int* location;
int* stype;
int n;

int cdist(int i, int j)
{
    if (i == j) return 0;
    if (dist[i][j] == 0)
    {
        dist[i][j] = getDistance(i, j);
        dist[j][i] = dist[i][j];
    }
    return dist[i][j];
}

int getNext(int x)
{
    int mi = M;
    int next = -1;
    for (int i = 0; i < n; i++)
    {
        if (cdist(x, i) < mi && i != x)
        {
            mi = cdist(x, i);
            next = i;
        }
    }

    if (next != -1)
    {
        if (stype[x] == 1)
        {
            location[next] = location[x] + mi;
            stype[next] = 2;
        } else
        {
            location[next] = location[x] - mi;
            stype[next] = 1;
        }
    }

    return next;
}

void makeNew()
{
    for (int i = 0; i < N; i++)
    {
        distNow[i] = M;
    }
}

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

    if (n == 1) return;




    int l = 0;
    int cur = getNext(l);
    l = getNext(cur);
    makeNew();
    while (true)
    {
        int cur = getNext(l);

        int cl = -1;
        int mi = M;
        for (int i = 0; i < n; i++)
        {
            distNow[i] = min(distNow[i], cdist(l, i));
            if (cdist(cur, i) < mi && cdist(cur, i) > cdist(l, cur) && distNow[i] > cdist(cur, i))
            {
                cl = i;
                mi = cdist(cur, i);
            }
        }


        if (cl == -1)
        {
            break;
        } else
        {
            l = cl;
            location[l] = location[cur] - mi;
            stype[l] = 1;
        }
    }


    int ml = l;

    int r = getNext(ml);


    makeNew();

    while (true)
    {
        int cur = getNext(r);
        int cr = -1;
        int mi = M;
        for (int i = 0; i < n; i++)
        {
            distNow[i] = min(distNow[i], cdist(r, i));
            if (cdist(cur, i) < mi && cdist(cur, i) > cdist(r, cur) && distNow[i] > cdist(cur, i))
            {
                cr = i;
                mi = cdist(cur, i);
            }
        }

        if (cr == -1)
        {
            break;
        } else
        {
            r = cr;
            location[r] = location[cur] + mi;
            stype[r] = 2;
        }
    }



    int mr = r;
    l = getNext(r);
    makeNew();
    while (true)
    {
        int cur = getNext(l);

        int cl = -1;
        int mi = M;
        for (int i = 0; i < n; i++)
        {
            distNow[i] = min(distNow[i], cdist(l, i));
            if (cdist(cur, i) < mi && cdist(cur, i) > cdist(l, cur) && distNow[i] > cdist(cur, i))
            {
                cl = i;
                mi = cdist(cur, i);
            }
        }

        if (cl == -1)
        {
            break;
        } else
        {
            l = cl;
            location[l] = location[cur] - mi;
            stype[l] = 1;
        }
    }


}

Compilation message (stderr)

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

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