Submission #821668

#	Time	Username	Problem	Language	Result	Execution time	Memory
821668		thimote75	Rail (IOI14_rail)	C++14	8 / 100	44 ms	512 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;

bdata isD1;

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 curDP = minP;
    location[curDP] = minD + first;
    stype   [curDP] = 2;

    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 off  = distance0[curDP] + getDistance(curDP, next);
        int res  = distance0[next];

        if (off == res) continue ;

        curDP = next;
        location[curDP] = first + distance0[curDP];
        stype   [curDP] = 2;
    }
}

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