Submission #824069

#	Time	Username	Problem	Language	Result	Execution time	Memory
824069		drdilyor	Stations (IOI20_stations)	C++17	100 / 100	760 ms	760 KiB

stations

#include<bits/stdc++.h>
#include "stations.h"
using namespace std;
using ll = long long;

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n), subs(n);
    vector<vector<int>> adj(n);
    for (int i = 0; i < n - 1; i++)
        adj[u[i]].push_back(v[i]),
        adj[v[i]].push_back(u[i]);

    auto dfs_s = [&](auto& dfs, int i, int p)->void {
        subs[i] = 1;
        for (int e : adj[i]) {
            if (e != p) {
                dfs(dfs, e, i);
                subs[i] += subs[e];
            }
        }
    };
    dfs_s(dfs_s, 0, -1);

    auto dfs = [&](auto& dfs, int i, int p, int dep, int l, int r)->void {
        for (int e : adj[i]) {
            if (e == p) continue;
            int nl, nr;
            if (dep % 2 == 0) {
                nl = r - subs[e] + 1;
                nr = r;
                r -= subs[e];
            } else {
                nl = l;
                nr = l + subs[e] - 1;
                l += subs[e];
            }
            dfs(dfs, e, i, dep+1, nl, nr);
        }
        assert(l == r);
        labels[i] = l;
    };
    dfs(dfs, 0, -1, 0, 0, n-1);
    // for (int i : labels) cout << i << ' '; cout << endl;
    return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
    sort(c.begin(), c.end());
    if (s == 0) {// root
        for (int i : c) {
            if (t <= i) return i;
        }
        assert(false);
    }
    
    if (c[0] < s) { // left-right-left
        int par = c[0];
        if (s < t) return par;
        c.erase(c.begin());
        reverse(c.begin(), c.end());
        for (int j : c) {
            if (j <= t) return j;
        }
        return par;
    } else {//right-left-right
        reverse(c.begin(), c.end());
        int par = c[0];
        if (t < s) return par;
        c.erase(c.begin());
        reverse(c.begin(), c.end());
        for (int j : c) {
            if (t <= j) return j;
        }
        return par;
    }
}

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