제출 #1364913

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

#if 0

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

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

    for (int n = 2; n <= 100; n++) {
        auto labels = label(n,0,edge1,edge2);

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

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                int currentIndex = i+1;
                while (currentIndex != j+1) {
                    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+1,values);
                }
            }
        }
    }
}

#endif

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