Submission #1241018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241018		franuch	Stations (IOI20_stations)	C++20	100 / 100	307 ms	640 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back

vc<ll> label(ll n, ll k, vc<ll> u, vc<ll> v) {
    vc<vc<ll>> g(n);
    for (ll i = 0; i < n - 1; i++) {
        g[u[i]].pub(v[i]);
        g[v[i]].pub(u[i]);
    }
    
    ll tim = 0;
    vc<ll> ret(n);
    function<void(ll, ll, ll)> dfs = [&](ll v, ll p, ll lvl) {
        if (lvl == 0)
            ret[v] = tim;
        tim++;
        for (ll w : g[v]) {
            if (w == p)
                continue;
            dfs(w, v, lvl ^ 1);
            tim++;
        }
        if (lvl == 1)
            ret[v] = tim - 1;
    };
    dfs(0, -1, 0);
    
    map<ll, ll> mp;
    for (ll v = 0; v < n; v++)
        mp[ret[v]] = 0;
    tim = 0;
    for (auto &[x, i] : mp)
        i = tim++;
    for (ll v = 0; v < n; v++)
        ret[v] = mp[ret[v]];
    
    return ret;
}

ll find_next_station(ll s, ll t, vc<ll> c) {
	if (sz(c) == 1)
	    return c[0];
	sort(all(c));
	ll d = sz(c);
	if (s < c[0]) {
	    ll prv = s;
	    for (ll i = 0; i < d - 1; i++) {
	        if (prv < t and t <= c[i])
	            return c[i];
            prv = c[i];
	    }
	    return c[d - 1];
	} else {
	    ll prv = s;
	    for (ll i = d - 1; i >= 1; i--) {
	        if (c[i] <= t and t < prv)
	            return c[i];
	        prv = c[i];
	    }
	    return c[0];
	}
}

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