Submission #634355

#	Time	Username	Problem	Language	Result	Execution time	Memory
634355		tabr	Stations (IOI20_stations)	C++17	100 / 100	880 ms	832 KiB

stations

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

// editorial?

vector<int> label(int n, int k, vector<int> x, vector<int> y) {
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) {
        g[x[i]].emplace_back(y[i]);
        g[y[i]].emplace_back(x[i]);
    }
    vector<int> depth(n), sz(n);
    {
        function<void(int, int)> Dfs = [&](int v, int p) {
            sz[v]++;
            for (int to : g[v]) {
                if (to == p) {
                    continue;
                }
                depth[to] = depth[v] + 1;
                Dfs(to, v);
                sz[v] += sz[to];
            }
        };
        Dfs(0, -1);
    }
    vector<int> res(n);
    function<void(int, int, int, int)> Dfs = [&](int v, int p, int low, int high) {
        if (depth[v] % 2 == 0) {
            res[v] = low;
            low++;
        } else {
            res[v] = high - 1;
            high--;
        }
        for (int to : g[v]) {
            if (to == p) {
                continue;
            }
            Dfs(to, v, low, low + sz[to]);
            low += sz[to];
        }
        assert(low == high);
    };
    Dfs(0, -1, 0, n);
    return res;
}

int find_next_station(int s, int t, vector<int> c) {
    sort(c.begin(), c.end());
    if (c[0] < s) {
        reverse(c.begin(), c.end());
        for (int v : c) {
            if (v <= t && t < s) {
                return v;
            }
        }
    } else {
        for (int v : c) {
            if (s < t && t <= v) {
                return v;
            }
        }
    }
    return c.back();
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    return 0;
}
#endif

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 16 / 16
• Subtask 4: 10 / 10
• Subtask 5: 61 / 61