Submission #1230284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230284		badge881	Stations (IOI20_stations)	C++20	100 / 100	305 ms	588 KiB

stations

#include <bits/stdc++.h>
#ifndef HOME
#include "stations.h"
#endif
using namespace std;

vector<int> label(int n, int _, vector<int> u, vector<int> v)
{
    int cnt = 0;
    vector<int> ans(n, 0);
    vector<bool> vu(n, false);
    vector<vector<int>> listAdj(n);
    for (int i = 0; i < n - 1; i++)
    {
        listAdj[u[i]].push_back(v[i]);
        listAdj[v[i]].push_back(u[i]);
    }

    function<void(int, bool)> dfs = [&](int node, bool b)
    {
        if (vu[node])
            return;
        vu[node] = true;
        if (b)
            ans[node] = cnt++;
        for (auto &&voisin : listAdj[node])
            dfs(voisin, !b);
        if (!b)
            ans[node] = cnt++;
    };
    dfs(0, false);
    return ans;
}
int find_next_station(int start, int target, std::vector<int> voisins)
{
    sort(voisins.begin(), voisins.end());
    if (start > voisins[0]) // current is biggest
    {
        if (target > start || target < voisins[0])
            return voisins[0];

        auto it = upper_bound(voisins.begin(), voisins.end(), target);
        if (it != voisins.begin())
            it--;

        return *it;
    }
    else // current is smallest
    {
        if (target < start || target > voisins.back())
            return voisins.back();

        auto it = lower_bound(voisins.begin(), voisins.end(), target);
        if (it == voisins.end())
            it--;
        return *it;
    }
}

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