Submission #282522

#	Time	Username	Problem	Language	Result	Execution time	Memory
282522		Kastanda	Rail (IOI14_rail)	C++11	30 / 100	141 ms	98552 KiB

rail

// M
#include<bits/stdc++.h>
#include "rail.h"
using namespace std;
const int N = 5005;
int n, D[N][N];
int Dist(int i, int j)
{
        if (D[i][j] == -1)
                D[i][j] = getDistance(i, j);
        return D[i][j];
}

void findLocation(int _n, int loc0, int location[], int stype[])
{
        n = _n;
        location[0] = loc0;
        stype[0] = 1;
        memset(D, -1, sizeof(D));
        for (int i = 0; i < n; i ++)
                D[i][i] = 0;

        int nw = 1;
        for (int i = 1; i < n; i ++)
                if (Dist(0, i) < Dist(0, nw))
                        nw = i;

        location[nw] = location[0] + Dist(0, nw);
        stype[nw] = 2;

        vector < int > L, R;
        for (int i = 1; i < n; i ++)
                if (i != nw && Dist(0, nw) + Dist(nw, i) == Dist(0, i))
                        L.push_back(i);
                else if (i != nw)
                        R.push_back(i);
        L.push_back(0);
        sort(L.begin(), L.end(), [&](int i, int j){return Dist(nw, i) < Dist(nw, j);});

        int now = nw, last = -1;
        for (int i : L)
        {
                if (last == -1)
                {
                        stype[i] = 1;
                        location[i] = location[nw] - Dist(nw, i);
                        last = i;
                        continue;
                }
                if (Dist(last, i) < location[now] - location[last])
                {
                        now = i;
                        stype[now] = 2;
                        location[now] = location[last] + Dist(last, i);
                        continue;
                }
                else
                {
                        stype[i] = 1;
                        location[i] = location[nw] - Dist(nw, i);
                        last = i;
                }
        }

        int st = L[0];
        for (int i : R)
                D[st][i] = Dist(nw, i) - Dist(nw, st);
        sort(R.begin(), R.end(), [&](int i, int j){return Dist(st, i) < Dist(st, j);});
        now = st;
        last = -1;
        for (int i : R)
        {
                if (last == -1)
                {
                        stype[i] = 2;
                        location[i] = location[st] + Dist(st, i);
                        last = i;
                        continue;
                }
                if (Dist(last, i) < location[last] - location[now])
                {
                        now = i;
                        stype[now] = 1;
                        location[now] = location[last] - Dist(last, i);
                        continue;
                }
                else
                {
                        stype[i] = 2;
                        location[i] = location[st] + Dist(st, i);
                        last = i;
                }
        }
        return ;
}

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