Submission #687639

#	Time	Username	Problem	Language	Result	Execution time	Memory
687639		urosk	Stations (IOI20_stations)	C++14	0 / 100	896 ms	544 KiB

stations

#include "stations.h"
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include "bits/stdc++.h"
#define ld double
#define ll int
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

using namespace std;

vector<ll> label(ll N, ll K,vector<ll> u,vector<ll> v){
    ll n = N;
    vector<vector<ll> > g(n);
    vector<ll> in(n),out(n),par(n);
    ll ti = 0;
    for(ll i = 0;i<n-1;i++){
        ll x = u[i],y = v[i];
        g[x].pb(y);
        g[y].pb(x);
    }
    queue<ll> q;
    q.push(1);
    vector<bool> vis(n);
    while(sz(q)){
        ll u = q.front();
        vis[u] = 1;
        in[u] = ++ti;
        while(sz(g[u])){
            ll s = g[u].back();
            g[u].popb();
            if(vis[s]) continue;
            par[s] = u;
            q.push(s);
            goto lol;
        }
        q.pop();
        lol:;
    }
    vector<ll> ans(n);
    for(ll i = 0;i<n;i++) ans[i] = in[i];
	return ans;
}
bool intree(ll v,ll u){
    ll inu = u/1000,outu = u%1000;
    ll inv = v/1000,outv = v%1000;
    return inu<=inv&&outu>=outv;
}
ll find_next_station(ll u, ll v, vector<ll> w){
    sort(all(w));
    for(ll i = 1;i<sz(w)-1;i++){
        if(v<w[i+1]&&v>w[i]) return v;
    }
	return w[0];
}
/**
1
5 1000000000
0 1
1 2
1 3
2 4
2
2 0 0
1 3 0
ans:
1
3
**/

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