Submission #282575

#	Time	Username	Problem	Language	Result	Execution time	Memory
282575		Kastanda	Rail (IOI14_rail)	C++11	100 / 100	157 ms	98656 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)
        {
                if (D[j][i] == -1)
                        D[i][j] = D[j][i] = getDistance(i, j);
                D[i][j] = D[j][i];
        }
        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);});

        vector < int > vec;
        for (int i : L)
        {
                if (!vec.size())
                {
                        stype[i] = 1;
                        location[i] = location[nw] - Dist(nw, i);
                        vec.push_back(i);
                        continue;
                }
                int loc = location[vec.back()] + Dist(vec.back(), i);
                if (loc < location[nw])
                {
                        int le = -1, ri = (int)vec.size() - 1, md;
                        while (ri - le > 1)
                        {
                                md = (le + ri) >> 1;
                                if (location[vec[md]] <= loc)
                                        ri = md;
                                else
                                        le = md;
                        }
                        if (location[vec[ri]] < loc && Dist(nw, vec[ri]) + loc - location[vec[ri]] == Dist(nw, i))
                        {
                                stype[i] = 2;
                                location[i] = loc;
                                continue;
                        }
                }
                stype[i] = 1;
                location[i] = location[nw] - Dist(nw, i);
                vec.push_back(i);
        }

        int st = L[0];
        for (int i : R)
                D[st][i] = D[i][st] = Dist(nw, i) - Dist(nw, st);
        sort(R.begin(), R.end(), [&](int i, int j){return Dist(st, i) < Dist(st, j);});
        vec.clear();
        for (int i : R)
        {
                if (!vec.size())
                {
                        stype[i] = 2;
                        location[i] = location[st] + Dist(st, i);
                        vec.push_back(i);
                        continue;
                }
                int loc = location[vec.back()] - Dist(vec.back(), i);
                if (loc > location[st])
                {
                        int le = -1, ri = (int)vec.size() - 1, md;
                        while (ri - le > 1)
                        {
                                md = (le + ri) >> 1;
                                if (location[vec[md]] >= loc)
                                        ri = md;
                                else
                                        le = md;
                        }
                        if (location[vec[ri]] > loc && Dist(st, vec[ri]) + location[vec[ri]] - loc == Dist(st, i))
                        {
                                stype[i] = 1;
                                location[i] = loc;
                                continue;
                        }
                }
                stype[i] = 2;
                location[i] = location[st] + Dist(st, i);
                vec.push_back(i);
        }
        return ;
}

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