제출 #1214832

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1214832		biank	기지국 (IOI20_stations)	C++20	100 / 100	312 ms	580 KiB

stations

#include <bits/stdc++.h>

using namespace std;

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

const int MAX_N = 1000;

typedef vector<int> vi;
#define pb push_back

vi adj[MAX_N];
int in[MAX_N], out[MAX_N];
int height[MAX_N], timer = 0;

void dfs(int u, int h = 0, int p = -1) {
    height[u] = h;
    in[u] = timer++;
    for (int v : adj[u]) {
        if (v != p) dfs(v, h + 1, u);
    }
    out[u] = timer++;
}

vi label(int n, int k, vi u, vi v) {
    for (int i = 0; i < n; i++) {
        adj[i].clear();
    }
    for (int i = 0; i < n - 1; i++) {
        adj[u[i]].pb(v[i]);
        adj[v[i]].pb(u[i]);
    }
    dfs(0);
    vi l(n);
    for (int i = 0; i < n; i++) {
        if (height[i] % 2 == 0) {
            l[i] = in[i];
        } else {
            l[i] = out[i];
        }
    }
    vi vals = l;
    sort(all(vals));
    for (int i = 0; i < n; i++) {
        l[i] = int(lower_bound(all(vals), l[i]) - begin(vals));
    }
    return l;
}
int find_next_station(int s, int t, vi c) {
    const int g = sz(c);
    int par = -1;
    vi c_in, c_out;
    if (s < c.back()) {
        par = s == 0 ? -1 : c.back();
        c_out = c;
        c_in.resize(g);
        c_in[0] = s + 1;
        for (int i = 1; i < g; i++) {
            c_in[i] = c_out[i - 1] + 1;
        }
    } else {
        par = c.front();
        c_in = c;
        c_out.resize(g);
        c_out[g - 1] = s - 1;
        for (int i = g - 2; i >= 0; i--) {
            c_out[i] = c_in[i + 1] - 1;
        }
    }
    for (int i = 0; i < g; i++) {
        if (c[i] != par && c_in[i] <= t && t <= c_out[i]) {
            return c[i];
        }
    }
    return par;
}

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