Submission #160600

#	Time	Username	Problem	Language	Result	Execution time	Memory
160600		rama_pang	Rail (IOI14_rail)	C++14	56 / 100	848 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_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;
        for (auto c : curC) 
            if (distance(pivotD, i) == distance(pivotD, c) + distance(c, 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] + distance(turnback, i);
            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;
        for (auto d : curD) 
            if (distance(pivotC, i) == distance(pivotC, d) + distance(d, 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] - distance(turnback, i);
            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];

    // for (int i = 0; i < N; i++) cout << type[i] << " ";
    // cout << "\n";
    // for (int i = 0; i < N; i++) cout << station[i] << " ";
    // cout << "\n";

    return;
}

/*

2
11
1 10
1 3
2 6
2 7
1 1
1 37
2 48
1 11
2 22
1 0
2 100


*/

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