Submission #379505

#	Time	Username	Problem	Language	Result	Execution time	Memory
379505		rocks03	Stations (IOI20_stations)	C++14	100 / 100	1125 ms	1308 KiB

stations

//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 1e3;
vector<int> g[MAXN];

int timer, tin[MAXN], tou[MAXN];
void dfs(int v, int d, vector<int>& labels){
    tin[v] = timer++;
    for(int u : g[v]){
        g[u].erase(find(all(g[u]), v));
        dfs(u, d ^ 1, labels);
    }
    tou[v] = timer++;
    if(d & 1) labels[v] = tou[v];
    else labels[v] = tin[v];
}

vector<int> label(int N, int K, vector<int> u, vector<int> v){
    rep(i, 0, N){
        g[i].clear();
    }
    auto add_edge = [&](int a, int b){
        g[a].pb(b);
        g[b].pb(a);
    };
    rep(i, 0, N - 1){
        add_edge(u[i], v[i]);
    }
    vector<int> labels(N);
    timer = 0;
    dfs(0, 0, labels);
    vector<pii> b(N);
    rep(i, 0, N){
        b[i] = {labels[i], i};
    }
    sort(all(b));
    rep(i, 0, N){
        labels[b[i].ss] = i;
    }
    return labels;
}

int find_next_station(int s, int t, vector<int> c){
    bool tin = true, tou = true;
    for(int x : c){
        tin &= (s < x);
        tou &= (s > x);
    }
    if(tin){
        sort(all(c));
        rep(i, 0, SZ(c) - 1){
            if(s <= t && t <= c[i]){
                return c[i];
            }
        }
        return c.back();
    } else if(tou){
        sort(all(c), greater<int>());
        rep(i, 0, SZ(c) - 1){
            if(c[i] <= t && t <= s){
                return c[i];
            }
        }
        return c.back();
    }
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
   83 | }
      | ^

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