제출 #160571

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
160571		rama_pang	철로 (IOI14_rail)	C++14	56 / 100	743 ms	150876 KiB

rail

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

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

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

void solve_left(int c, int d, vector<int> candidates);

void solve_right(int c, int d, vector<int> candidates) {
    if (candidates.empty()) return;

    int new_c = c, new_d = candidates.front();
    vector<int> le, ri;

    for (auto i : candidates) {
        if (i == c || i == d) continue;
        if (G[c][i] < G[c][new_d]) new_d = i;
    }

    for (auto i : candidates) {
        if (i == new_c || i == new_d) continue;
        if (G[new_d][i] < G[new_d][new_c]) new_c = i;
    }

    for (auto i : candidates) {
        if (i == new_c || i == new_d) continue;
        if (G[new_c][i] == G[new_d][i] + G[new_c][new_d]) le.push_back(i);
        if (G[new_d][i] == G[new_c][i] + G[new_c][new_d]) ri.push_back(i);
    }

    type[new_c] = C_STATION;
    type[new_d] = D_STATION;
    station[new_d] = station[c] + G[c][new_d];
    station[new_c] = station[new_d] - G[new_d][new_c];

    solve_left(new_c, new_d, le);
    solve_right(new_c, new_d, ri);
}

void solve_left(int c, int d, vector<int> candidates) {
    if (candidates.empty()) return;

    int new_d = d, new_c = candidates.front();
    vector<int> le, ri;

    for (auto i : candidates) {
        if (i == c || i == d) continue;
        if (G[d][i] < G[d][new_c]) new_c = i;
    }

    for (auto i : candidates) {
        if (i == new_c || i == new_d) continue;
        if (G[new_c][i] < G[new_c][new_d]) new_d = i;
    }

    for (auto i : candidates) {
        if (i == new_c || i == new_d) continue;
        if (G[new_d][i] == G[new_c][i] + G[new_c][new_d]) ri.push_back(i);
        if (G[new_c][i] == G[new_d][i] + G[new_c][new_d]) le.push_back(i);
    }

    type[new_c] = C_STATION;
    type[new_d] = D_STATION;
    station[new_c] = station[d] - G[d][new_c];
    station[new_d] = station[new_c] + G[new_d][new_c];

    solve_left(new_c, new_d, le);
    solve_right(new_c, new_d, ri);
}

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

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (G[i][j] != -1) continue;
            G[i][j] = G[j][i] = (i == j)? 0 : getDistance(i, j);
        }
    }

    int d = 1;
    for (int i = 0; i < N; i++) {
        if (i == 0) continue;
        if (G[0][d] > G[0][i]) d = i;
    }

    int c = 0;
    for (int i = 0; i < N; i++) {
        if (i == d) continue;
        if (G[d][c] > G[d][i]) c = i;
    }

    vector<int> le, ri;
    for (int i = 0; i < N; i++) {
        if (i == c || i == d) continue;
        if (G[c][i] == G[d][i] + G[c][d]) le.push_back(i);
        if (G[d][i] == G[c][i] + G[c][d]) ri.push_back(i);
    }

    type[d] = D_STATION;
    type[c] = C_STATION;
    station[d] = station[0] + G[0][d];
    station[c] = station[d] - G[c][d];

    solve_right(c, d, ri);
    solve_left(c, d, le);

    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: 0 / 44