Submission #1229941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229941		a4n_	Stations (IOI20_stations)	C++20	100 / 100	314 ms	7616 KiB

stations

#include <bits/stdc++.h>
#include "stations.h"
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
 
const int N = 3e5 + 100, lg = 18;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
 
ll MOD(ll a, ll mod=Mod) {
    a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
    ll res = 1;
    while(b > 0) {
        if(b%2 == 1) res = MOD(res * a, mod);
        b /= 2;
        a = MOD(a * a, mod);
    }
    return res;
}
 
int n, tin[N], h[N], tout[N], cnt, ans[N];
vector<int> adj[N];

void dfs(int v, int p=-1) {
    if(h[v] == 0) ans[v] = cnt++;
    for(int u : adj[v]) {
        if(u == p) continue;
        h[u] = 1 - h[v];
        dfs(u,v);
    }
    if(h[v] == 1) ans[v] = cnt ++;
}

vector<int> label(int _n, int _k, vector<int> eu, vector<int> ev) {
    n = _n;
    cnt = 0;
    
    for(int i=0; i<n-1; i++) {
        adj[eu[i]].pb(ev[i]);
        adj[ev[i]].pb(eu[i]);
    }

    dfs(0);
    vector<int> res;
    for(int i=0; i<n; i++) {
        res.pb(ans[i]);
        // fuck(ans[i]);
    }
    for(int i=0; i<n; i++) adj[i].clear();
    return res;
}

int find_next_station(int s, int t, vector<int> c) {
    if(size(c) == 1) return c[0];

    if(s <= c[0]) {
        if(t < s) return c.back();
        for(int i=0; i<size(c); i++) {
            if(t <= c[i]) return c[i];
        }
        return c.back();
    }

    if(t > s) return c[0];
    for(int i=size(c)-1; i>=0; i--) {
        if(t >= c[i]) return c[i];
    }
    return c[0];
}

// int main() {
//     label(5, 10, {0, 1, 1, 2}, {1, 2, 3, 4});
//     // find_next_station()

//     return 0;
// }

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