Submission #804698

#	Time	Username	Problem	Language	Result	Execution time	Memory
804698		PixelCat	Stations (IOI20_stations)	C++14	0 / 100	775 ms	840 KiB

stations

#include "stations.h"

#ifdef NYAOWO
#include "stub.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 1000;

vector<int> adj[MAXN + 10];
int ids[MAXN + 10];
int siz[MAXN + 10];

void dfs(int n, int p) {
    static int cur_id = 0;
    ids[n] = cur_id;
    cur_id++;
    siz[n] = 0;
    for(auto &i:adj[n]) if(i != p) {
        dfs(i, n);
        siz[n] += siz[i] + 1;
    }
}

int encode(int id, int sz) {
    return id * MAXN + sz;
}
int encode(pii p) {
    return encode(p.F, p.S);
}
pii decode(int x) {
    return pii(x / MAXN, x % MAXN);
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    For(i, 0, n - 1) {
        adj[i].clear();
    }
    int m = sz(u);
    For(i, 0, m - 1) {
        adj[u[i]].eb(v[i]);
        adj[v[i]].eb(u[i]);
    }
    dfs(0, 0);
    vector<int> labels(n);
    For(i, 0, n - 1) {
        labels[i] = encode(ids[i], siz[i]);
    }
    return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
    if(sz(c) == 1) return c[0];
    
    vector<pii> v;  // {id, sz}
    for(auto &x:c) v.eb(decode(x));
    sort(all(v));

    int n = sz(v);

    int id = v[1].F - 1;
    int sz = 0;
    For(i, 1, n - 1) sz += v[i].S;
    
    pii pt = decode(t);
    if(pt.F < id || pt.F > id + sz) return encode(v[0]);
    For(i, 1, n - 2) {
        if(pt.F < v[i + 1].F) return encode(v[i]);
    }
    return encode(v[n - 1]);
}

/*

1
5 10
0 1
1 2
1 3
2 4
2
2 0 1
1 3 3

*/

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