Submission #160692

#	Time	Username	Problem	Language	Result	Execution time	Memory
160692		rama_pang	Rail (IOI14_rail)	C++14	100 / 100	207 ms	98936 KiB

rail

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

const int C_STATION = 1;
const int D_STATION = 2;

int N;
vector<int> station, type;
vector<vector<int>> G;

inline int distance(int a, int b) {
    if (a == b) G[a][b] = 0;
    if (G[a][b] == -1) G[a][b] = G[b][a] = getDistance(a, b);
    return G[a][b];
}

void solve(int pivot, vector<int> candidate) {
    if (candidate.empty()) return;

    const int SAME_TYPE = type[pivot];
    const int DIFF_TYPE = (type[pivot] == C_STATION)? D_STATION : C_STATION;
    const int SIGN = (SAME_TYPE == C_STATION)? +1 : -1;

    vector<int> cur;
    cur.push_back(candidate.front());
    candidate.erase(candidate.begin());
    station[cur[0]] = station[pivot] + SIGN * distance(pivot, cur[0]);
    type[cur[0]] = DIFF_TYPE;

    for (auto i : candidate) {
        int turnback = -1;
        int last = cur.back();

        for (auto c : cur) 
            if (distance(pivot, i) == distance(pivot, c) + distance(last, i) - SIGN * (station[last] - station[c])) 
                turnback = c;

        if (turnback == -1) {
            cur.push_back(i);
            type[i] = DIFF_TYPE;
            station[i] = station[pivot] + SIGN * distance(pivot, i);
        } else {
            type[i] = SAME_TYPE;
            station[i] = station[pivot] + SIGN * (distance(pivot, i) - 2 * (distance(last, i) - SIGN * (station[last] - station[turnback])));
        }
    }

}

void findLocation(int N_, int first_, int location[], int stype[]) {
    N = N_, station.resize(N), type.resize(N);
    G.assign(N, vector<int>(N, -1));
    station[0] = first_, type[0] = C_STATION;

    int pivotC = 0, pivotD = 1;
    for (int i = 0; i < N; i++) if (i != pivotC && distance(pivotC, pivotD) > distance(pivotC, i)) pivotD = i;
    station[pivotD] = station[pivotC] + distance(pivotC, pivotD); 
    type[pivotD] = D_STATION;

    vector<int> Lside, Rside;
    for (int i = 0; i < N; i++) {
        if (i == pivotC || i == pivotD) continue;
        if (distance(pivotC, i) == distance(pivotC, pivotD) + distance(pivotD, i)) 
            Lside.push_back(i);
        else 
            Rside.push_back(i);
    }

    /* Filter Lside stations from stations that is between pivotC...pivotD */
    for (vector<int> tmp; tmp.empty() && !Lside.empty();) {
        for (auto i : Lside) {
            if (distance(pivotD, i) <= distance(pivotD, pivotC)) {
                station[i] = station[pivotD] - distance(pivotD, i);
                type[i] = C_STATION;
            } else {
                tmp.push_back(i);
            }
        }
        Lside = tmp;
        break;
    }

    sort(Rside.begin(), Rside.end(), [&](int l, int r) { return distance(pivotC, l) < distance(pivotC, r); });
    sort(Lside.begin(), Lside.end(), [&](int l, int r) { return distance(pivotD, l) < distance(pivotD, r); });

    solve(pivotC, Rside);
    solve(pivotD, Lside);

    for (int i = 0; i < N; i++) stype[i] = type[i];
    for (int i = 0; i < N; i++) location[i] = station[i];

    return;
}

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