Submission #1230231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230231		badge881	기지국 (IOI20_stations)	C++20	0 / 100	308 ms	568 KiB

stations

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

vector<int> label(int n, int _, vector<int> u, vector<int> v)
{
    int cnt = 0;
    vector<int> ans(n);
    vector<bool> vu(n, false);
    vector<vector<int>> listAdj(n);
    for (int i = 0; i < n; 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, true);
    return ans;
}

int find_next_station(int start, int target, 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: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 16
• Subtask 4: 0 / 10
• Subtask 5: 0 / 61