제출 #1364940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1364940		backer8002	기지국 (IOI20_stations)	C++20	69.87 / 100	292 ms	612 KiB

stations

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

static void DFS(int curr, int prev, vector<int> &res, bool maximum, const vector<vector<int> > &edges) {
    static int time = 0;
    if (!maximum)
        res[curr] = time++;

    for (int edge: edges[curr])
        if (edge != prev)
            DFS(edge, curr, res, !maximum, edges);

    if (maximum)
        res[curr] = time++;
}

vector<int> label(int n, int, vector<int> u, vector<int> v) {
    vector<vector<int> > edges(n);
    for (int i = 0; i < n - 1; i++) {
        edges[u[i]].emplace_back(v[i]);
        edges[v[i]].emplace_back(u[i]);
    }
    vector<int> res(n);
    DFS(0, 0, res, false, edges);
    return res;
}

int find_next_station(int s, int t, vector<int> c) {
    if (s < c[0]) {
        if (t >= c.back() || t < s)
            return c.back();
        return *ranges::lower_bound(c, t);
    }
    if (t > s || t <= c[0])
        return c[0];
    return *--ranges::lower_bound(c, t+1);
}

#if 0

int main() {
    int n;
    cin >> n;
    vector<int> edge1(n), edge2(n);

    for (int i = 0; i < n - 1; i++) {
        edge1[i] = i;
        edge2[i] = i + 1;
    }

    auto labels = label(n, 0, edge1, edge2);

    map<int, int> mapping;
    for (int i = 0; i < n; i++)
        mapping[labels[i]] = i;

    for (auto [map,mapped]: mapping)
        println("{}, {}", map, mapped);
    int i,j;
    cin >> i >> j;
    int currentIndex = i;
    while (currentIndex != j) {
        vector<int> values;
        if (mapping[currentIndex] != 0)
            values.emplace_back(labels[mapping[currentIndex] - 1]);
        if (mapping[currentIndex] != n - 1)
            values.emplace_back(labels[mapping[currentIndex] + 1]);
        ranges::sort(values);
        currentIndex = find_next_station(currentIndex, j, values);
        cout << currentIndex << '\n';
    }
}

#endif

• 서브태스크 1: 0 / 5
• 서브태스크 2: 0 / 8
• 서브태스크 3: 16 / 16
• 서브태스크 4: 10 / 10
• 서브태스크 5: 43.868 / 61