Submission #821695

#	Time	Username	Problem	Language	Result	Execution time	Memory
821695		thimote75	Rail (IOI14_rail)	C++14	30 / 100	46 ms	624 KiB

rail

#include "rail.h"

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using bdata = vector<bool>;

template<typename T>
using lpq = priority_queue<T, vector<T>, greater<T>>;
using ii  = pair<int, int>;

idata distance0;

const int DTYPE = 2;
const int CTYPE = 1;

void findLocation(int N, int first, int location[], int stype[])
{
    location[0] = first;
    stype   [0] = 1;
    distance0.resize(N, -1);

    int minD = 1e9;
    int minP = -1;
    for (int i = 1; i < N; i ++) {
        distance0[i] = getDistance(0, i);

        if (distance0[i] >= minD) continue ;
        minD = distance0[i];
        minP = i;
    }

    int lefD = minP;
    int rigD = minP;
    location[minP] = first + minD;
    stype   [minP] = DTYPE;
    int lefC = -1;
    
    lpq<ii> queue;
    for (int i = 1; i < N; i ++)
        if (i != minP)
            queue.push({ distance0[i], i });

    while (queue.size() != 0) {
        const auto nextDP = queue.top(); queue.pop();

        int next = nextDP.second;

        int nextDist = getDistance(lefD, next);
        int offDist  = nextDist + minD;
        int resDist  = distance0[next];

        if (resDist == offDist) {
            bool isLefC = true;
            int passDist;
            if (lefC != -1) {
                passDist = getDistance(lefC, next);
                int offpDist = passDist + distance0[lefC];

                isLefC = resDist != offpDist;
            }

            if (isLefC) {
                lefC = next;
                location[next] = first + minD - nextDist;
                stype   [next] = CTYPE;
            } else {
                location[next] = passDist + location[lefC];
                stype   [next] = DTYPE;
            }
        } else {
            bool isRigD;

            int passDist = getDistance(rigD, next);
            int offpDist = passDist + distance0[rigD];
            isRigD = resDist != offpDist;

            if (isRigD) {
                rigD = next;
                location[next] = first + distance0[next];
                stype   [next] = DTYPE;
            } else {
                location[next] = location[rigD] - passDist;
                stype   [next] = CTYPE;
            }
        }
    }
}

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