Submission #160589

#	Time	Username	Problem	Language	Result	Execution time	Memory
160589		rama_pang	Rail (IOI14_rail)	C++14	0 / 100	336 ms	98652 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_left(int pivotC, int pivotD, vector<int> candidate) {
    if (candidate.empty()) return;

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

    vector<int> curC;

    for (auto i : candidate) {
        bool newC = true;
        int turnback = -1;
        int lastC = (curC.empty())? 0 : curC.back();

        for (auto c : curC) 
            if (distance(pivotD, i) == distance(pivotD, c) + abs(distance(c, lastC) - distance(lastC, i))) 
                newC = false, turnback = c;

        if (newC) {
            curC.push_back(i);
            station[i] = station[pivotD] - distance(pivotD, i);
            type[i] = C_STATION;
        } else {
            station[i] = station[turnback] + abs(distance(i, lastC) - distance(lastC, turnback));
            type[i] = D_STATION;
        }
    }
}

void solve_right(int pivotC, int pivotD, vector<int> candidate) {
    if (candidate.empty()) return;

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

    vector<int> curD;

    for (auto i : candidate) {
        bool newD = true;
        int turnback = -1;
        int lastD = (curD.empty())? 0 : curD.back();

        for (auto d : curD) 
            if (distance(pivotC, i) == distance(pivotC, d) + abs(distance(d, lastD) - distance(lastD, i))) 
                newD = false, turnback = d;
                
        if (newD) {
            curD.push_back(i);
            station[i] = station[pivotC] + distance(pivotC, i);
            type[i] = D_STATION;
        } else {
            station[i] = station[turnback] - abs(distance(i, lastD) - distance(lastD, turnback));
            type[i] = C_STATION;
        }
    }
}

void solve(int pivotC, int pivotD, vector<int> Lside, vector<int> Rside) {
    solve_left(pivotC, pivotD, Lside);
    solve_right(pivotC, pivotD, Rside);
    return;
}

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;

    for (int i = 0; i < N; i++) if (i != pivotD && distance(pivotD, pivotC) > distance(pivotD, i)) pivotC = i;
    station[pivotC] = station[pivotD] - distance(pivotD, pivotC);
    type[pivotC] = C_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);
        if (distance(pivotD, i) == distance(pivotD, pivotC) + distance(pivotC, i)) Rside.push_back(i);
    }

    solve(pivotC, pivotD, Lside, Rside);

    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: 0 / 8
• Subtask 2: 0 / 22
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44