Submission #687644

#	Time	Username	Problem	Language	Result	Execution time	Memory
687644		urosk	Stations (IOI20_stations)	C++14	52.32 / 100	905 ms	764 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;

#define maxn 1005
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);
    }
    function<void(ll,ll)> dfs = [&](ll u,ll p)
	{
        in[u] = ti++;
        for(ll s : g[u]) if(s!=p) dfs(s,u);
        out[u] = ti-1;
	};
	dfs(0,0);
    vector<ll> ans(n);
    for(ll i = 0;i<n;i++) ans[i] = in[i]*1000+out[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){
    ll p = -1;
    for(ll s : w){
        if(intree(u,s)) p = s;
    }
    for(ll s : w){
        if(s==p) continue;
        if(intree(v,s)) return s;
    }
	return p;
}
/**
1
5 1000000000
0 1
1 2
1 3
2 4
2
2 0 0
1 3 0
**/

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