oj.uz

답안 #160692

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
160692 2019-10-29T10:44:04 Z rama_pang 철로 (IOI14_rail) C++14
100 / 100
 207 ms 98936 KB 
#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.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 380 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 190 ms 98552 KB Output is correct
2 Correct 199 ms 98604 KB Output is correct
3 Correct 188 ms 98600 KB Output is correct
4 Correct 187 ms 98632 KB Output is correct
5 Correct 203 ms 98632 KB Output is correct
6 Correct 207 ms 98580 KB Output is correct
7 Correct 195 ms 98600 KB Output is correct
8 Correct 186 ms 98680 KB Output is correct
9 Correct 189 ms 98512 KB Output is correct
10 Correct 188 ms 98552 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 192 ms 98644 KB Output is correct
2 Correct 191 ms 98772 KB Output is correct
3 Correct 189 ms 98704 KB Output is correct
4 Correct 188 ms 98808 KB Output is correct
5 Correct 196 ms 98716 KB Output is correct
6 Correct 202 ms 98672 KB Output is correct
7 Correct 194 ms 98664 KB Output is correct
8 Correct 192 ms 98680 KB Output is correct
9 Correct 189 ms 98680 KB Output is correct
10 Correct 189 ms 98552 KB Output is correct
11 Correct 203 ms 98660 KB Output is correct
12 Correct 196 ms 98936 KB Output is correct
13 Correct 189 ms 98680 KB Output is correct
14 Correct 194 ms 98680 KB Output is correct
15 Correct 187 ms 98680 KB Output is correct
16 Correct 198 ms 98680 KB Output is correct
17 Correct 199 ms 98704 KB Output is correct
18 Correct 200 ms 98680 KB Output is correct
19 Correct 192 ms 98692 KB Output is correct
20 Correct 197 ms 98680 KB Output is correct