Submission #1125663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125663		jerzyk	Stations (IOI20_stations)	C++20	100 / 100	474 ms	588 KiB

stations

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

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1'007;
bool vis[N];
vector<int> ed[N];
int num[N];

void DFS(int v, int r, int &cnt)
{
    vis[v] = 1;
    if(r == 0)
        num[v] = cnt++;
    for(int i = 0; i < (int)ed[v].size(); ++i)
        if(!vis[ed[v][i]])
            DFS(ed[v][i], (r + 1) % 2, cnt);
    if(r == 1)
        num[v] = cnt++;
    //cerr << "DFS " << v << " " << num[v] << "\n";
}

vector<int> label(int _n, int _k, vector<int> _u, vector<int> _v)
{
    int n = _n;
    for(int i = 0; i < n - 1; ++i)
    {
        ed[_u[i]].pb(_v[i]);
        ed[_v[i]].pb(_u[i]);
    }
    vector<int> ans;
    int x = 0;
    DFS(0, 0, x);
    for(int i = 0; i < n; ++i)
        ans.pb(num[i]);
    for(int i = 0; i < n; ++i)
    {
        ed[i].clear();
        vis[i] = 0;
        num[i] = 0;
    }
    return ans;
}

int find_next_station(int _s, int _t, vector<int> _c)
{
    int v = _s, t = _t;
    vector<int> ne = _c;
    sort(ne.begin(), ne.end());
    if((int)ne.size() == 1)
        return ne[0];
    /*cerr << "Q: " << v << " " << t << "\n";
    for(int l = 0; l < (int)ne.size(); ++l)
        cerr << ne[l] << " ";
    cerr << "\n";*/
    if(ne[0] < v)
    {
        if(t < ne[1] || t > v) return ne[0];
        for(int l = 1; l < (int)ne.size() - 1; ++l)
            if(t >= ne[l] && t < ne[l + 1])
                return ne[l];
        return ne.back();
    }else
    {
        if(v != 0 && (t < v || t > ne[(int)ne.size() - 2])) return ne.back();
        int d = 0;
        if(v == 0) d = 1;
        for(int l = 0; l < (int)ne.size() - 1 + d; ++l)
            if(t <= ne[l])
                return ne[l];
        return -1;
    }
}

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