Submission #531477

#	Time	Username	Problem	Language	Result	Execution time	Memory
531477		sliviu	Stations (IOI20_stations)	C++17	100 / 100	947 ms	736 KiB

stations

#include <bits/stdc++.h>
#include <stations.h>

using namespace std;

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    int t = -1;
    vector<vector<int>> G(n);
    vector<int> sol(n);
    for (int i = 0; i < n - 1; ++i) {
        G[u[i]].emplace_back(v[i]);
        G[v[i]].emplace_back(u[i]);
    }
    function<void(int, int, int)> dfs = [&](int node, int last, int lvl) {
        if (!lvl)
            sol[node] = ++t;
        for (auto x : G[node])
            if (x != last)
                dfs(x, node, lvl ^ 1);
        if (lvl)
            sol[node] = ++t;
    };
    dfs(0, -1, 0);
    return sol;
}

int find_next_station(int s, int f, vector<int> adj) {
    int tins, touts, ft,mini=INT_MAX,maxi=0;
    int isin = 1;
    for (auto x : adj) {
        if (x < s)
            isin = 0;
        mini = min(mini, x);
        maxi = max(maxi, x);
    }
    if (isin)
        tins = s, ft = maxi, touts = ft - 1;
    else
        touts = s, ft = mini, tins = ft + 1;
    //cerr << ft << '\n';
    if (tins <= f && f <= touts) {
        int last = s;
        if (isin)
            sort(adj.begin(), adj.end());
        else
            sort(adj.begin(), adj.end(), greater<int>());
        for (auto x : adj)
            if (x != ft) {
                int curtin, curtout;
                if (isin)
                    curtout = x, curtin = last + 1, last = x;
                else
                    curtin = x, curtout = last - 1, last = x;
                //cerr << curtin << ' ' << curtout << '\n';
                if (curtin <= f && f <= curtout)
                    return x;
            }
    }
    return ft;
}

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