제출 #1364909

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1364909		backer8002	기지국 (IOI20_stations)	C++20	0 / 100	291 ms	588 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::upper_bound(c,t-1);
    }
    if (t > s)
        return c[0];
    return *--ranges::upper_bound(c,t);
}

#if 0

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

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

    int beginVal,endVal;
    cin >> beginVal >> endVal;

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

    int currentIndex = beginVal;
    while (currentIndex != endVal) {
        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,endVal,values);
    }
}

#endif

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