Submission #1229937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229937		a4n_	Stations (IOI20_stations)	C++20	0 / 100	8 ms	7612 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], c1, c2;
vector<int> adj[N];

void dfs(int v, int p=-1) {
    tin[v] = c1 ++;
    for(int u : adj[v]) {
        if(u == p) continue;
        h[u] = 1 - h[v];
        dfs(u,v);
    }
    tout[v] = c2 ++;
}

vector<int> label(int _n, int _k, vector<int> eu, vector<int> ev) {
    n = _n;
    c1 = c2 = 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++) {
        if(h[i] == 0) res.pb(tin[i]);
        else res.pb(tout[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: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 16
• Subtask 4: 0 / 10
• Subtask 5: 0 / 61