Submission #594997

#	Time	Username	Problem	Language	Result	Execution time	Memory
594997		MadokaMagicaFan	Stations (IOI20_stations)	C++14	0 / 100	3031 ms	2097152 KiB

stations

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;

#define all(v)          v.begin(),v.end()
#define sort(v)         sort(all(v))
#define endl            '\n'
#define forn(i,n)       for(int i = 0; i < n; ++i)
#define forbe(i,b,e)    for(int i = b; i < e; ++i)
#define forr(i,n)       for(int i = n-1; i >= 0; --i)
#define sz(v)           ((int)v.size())
#define pb              push_back
#define f               first
#define s               second

const int N = 1e3;
vi adj[N];
bitset<N> bip;

vi ret;

int cnt;

void dfs(int x, int p) {
    if (!bip[x])
        ret[x] = cnt++;

    for(int u : adj[x]) {
        if (u == p) continue;
        bip[u] = !bip[x];

        dfs(u, x);
    }

    if (bip[x])
        ret[x] = cnt++;
}

vi label(int n, int k, vi u, vi v) {
    cnt = 0;

    forn(i ,n-1) {
        adj[u[i]].pb(v[i]);
        adj[v[i]].pb(u[i]);
    }

    ret.assign(n,0);
    dfs(0,0);

    return ret;
}

int find_next_station(int s, int t, vi c) {
    if (s == t) return s;
    if (sz(c) == 1) return c[0];

    int mn, mx;

    mn = N;
    mx = 0;

    int p;

    for (int u : c)
    {
        mn = min(u, mn);
        mx = max(u, mx);
    }

    sort(c);

    if (mx > s) {
        p = mx;
        if (t < s) return p;
        if (t >= p) return p;
        reverse(all(c));
        forn(i, sz(c)) {
            if (c[i] < t)
                return c[i-1];
        }

        return c[sz(c)-1];
    } else {
        p = mn;
        if (t > s) return p;
        if (t <= p) return p;
        forn(i, sz(c)) {
            if (c[i] > t)
                return c[max(i-1,0)];
        }

        return c[sz(c)-1];
    }
}

#ifdef ONPC
void solve() {
    int n,k;
    cin >> n >> k;

    vi u(n-1), v(n-1);

    forn(i,n-1)
        cin >> u[i] >> v[i];

    vi l = label(n, k, u, v);

    forn(i, n)
        cout << l[i] << ' ';

        cout << endl;

//return;
    int q;
    cin >> q;

    while (q--) {
        int a, b;
        cin >> a >> b;

        vi c;

        for(int u : adj[a])
            c.pb(l[u]);
        
        cout << find_next_station(l[a], l[b], c) << endl;
    }
}

int main() {
    freopen("in", "r", stdin);
//    ios_base::sync_with_stdio(0);cin.tie(0);
    solve();
}
#endif

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