Submission #877514

#	Time	Username	Problem	Language	Result	Execution time	Memory
877514		vjudge1	Stations (IOI20_stations)	C++17	100 / 100	584 ms	1464 KiB

stations

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

#include "stations.h"

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
        vector<int> tin(n), tout(n), depth(n);
        int timer = 0;
        vector<vector<int>> adj(n);
        for (int i = 0; i < n - 1; i++) {
                adj[u[i]].emplace_back(v[i]);
                adj[v[i]].emplace_back(u[i]);
        }
        function<void(int, int)> dfs = [&](int u, int p) {
                tin[u] = timer;
                if (depth[u] == 0) timer++;
                for (int v : adj[u]) {
                        if (v == p) continue;
                        depth[v] = depth[u] ^ 1;
                        dfs(v, u);
                }
                tout[u] = timer;
                if (depth[u] == 1) timer++;
        };
        dfs(0, -1);
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
                ans[i] = depth[i] ? tout[i] : tin[i];
        }
        return ans;
}

int find_next_station(int s, int t, std::vector<int> c) {
        /// if (tin[s'] = s) <=> s < min_c
        /// if (tout[s'] = s) <=> s > max_c
        if (s < c[0]) {
                if (s == 0) {
                        /// s' = 0
                        return *lower_bound(c.begin(), c.end(), t);
                } else {
                        int touts = c.back();
                        int tins = s;
                        if (tins <= t && t <= touts) {
                                return *lower_bound(c.begin(), c.end(), t);
                        } else {
                                return c.back();
                        }
                }
        } else if (s > c.back()) {
                int tins = c[0];
                int touts = s;
                if (tins <= t && t <= touts) {
                        return *(--upper_bound(c.begin(), c.end(), t));
                } else {
                        return c[0];
                }
        } else {
                assert(0);
        }
}

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