Submission #828590

#	Time	Username	Problem	Language	Result	Execution time	Memory
828590		ALeonidou	Stations (IOI20_stations)	C++17	100 / 100	736 ms	876 KiB

stations

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

#define ll int
#define F first
#define S second
#define MID ((l+r)/2)
#define sz(x) (ll)x.size()
#define pb push_back
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;
typedef vector <ll> vi;
typedef pair<ll,ll> ii;
typedef vector <ii> vii;

void printVct(vi v){
    for (ll i =0; i<sz(v); i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
}

void printVctPair(vii v){
    for (ll i =0; i<sz(v); i++){
        cout<<"("<<v[i].F<<" "<<v[i].S<<"), ";
    }
    cout<<endl;
}

vector <vi> adj;
vi tin, tout, vis, labels;
ll dfsTimer = 0;
void dfs (ll u, bool parity){
    vis[u] = 1;
    tin[u] = dfsTimer;
    dfsTimer++;
    vis[u] = 1;
    for (ll i=0;i<sz(adj[u]); i++){
        if (!vis[adj[u][i]]){
            dfs(adj[u][i], !parity);
        }
    }
    tout[u] = dfsTimer;
    dfsTimer++;
    if (parity) labels[u] = tout[u];
    else labels[u] = tin[u];
}

vi label(int n, int k, vi u, vi v){
    adj.assign(n, vi());
    for (ll i =0; i<n-1; i++){
        adj[u[i]].pb(v[i]);
        adj[v[i]].pb(u[i]);
    }

    tin.resize(n);
    tout.resize(n);
    vis.assign(n, 0);
    labels.resize(n);

    dfs(0, 0);

    // cout<<"tin: ";
    // printVct(tin);

    // cout<<"tout: ";
    // printVct(tout);

    // cout<<"labels: ";
    // printVct(labels);

    vi labels_order(n);
    for (ll i =0; i<n ;i++) labels_order[i] = i;
    sort(labels_order.begin(), labels_order.end(), [&](ll a, ll b){ return (labels[a] < labels[b]);});

    // cout<<"labels_order: ";
    // printVct(labels_order);

    vi labels_rank(n);
    for (ll i = 0; i<n ;i++){
        labels_rank[labels_order[i]] = i;
    }

    // cout<<"labels_rank: ";
    // printVct(labels_rank);

    return labels_rank;
}

// ll calls = 0;
int find_next_station(int s, int t, vi c) {
    // calls++;
    // cout<<endl<<endl<<"-------"<<calls<<"-------";
    // dbg2(s,t);
    // cout<<"c: "; printVct(c);
    // cout<<endl;

	//STEP 1: Find in or out
    bool isin = (s < c[0]);
    // dbg(isin);

    //STEP 2: Find parent and remove
    ll p;
    sort(c.begin(), c.end());
    if (isin){
        p = c.back();
        c.pop_back();
    }
    else{
        p = c[0];
        c.erase(c.begin());
    }
    // dbg(p);

    //STEP 3: Find Range
    vii ranges;
    if (!isin){
        for (ll i = 0; i<sz(c)-1; i++){
            ranges.pb(ii(c[i], c[i+1]-1));
        }
        ranges.pb(ii(c.back(), s-1));
    }
    else{
        ranges.pb(ii(s+1, c[0]));
        for (ll i = 1; i<sz(c); i++){
            ranges.pb(ii(c[i-1]+1, c[i]));
        }
    }
    // cout<<"ranges: ";
    // printVctPair(ranges);

    //STEP 4: Solve
    ll ans = p;
    for (ll i =0; i<sz(ranges);i++){
        if (t >= ranges[i].F && t <= ranges[i].S){
            ans = c[i];
            break;
        }
    }
    // dbg(ans);

    return ans;
}

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