제출 #679683

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
679683		phoebe	기지국 (IOI20_stations)	C++17	100 / 100	892 ms	800 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 1e3 + 10;
int n, sz[maxn] = {0}, h[maxn], x[maxn] = {0}; // even = mn, odd = mx
vector<int> adj[maxn];
 
void dfs1(int v, int p, int height){
    h[v] = height; sz[v] = 1; 
    for (auto u : adj[v]){
        if (u == p) continue;
        dfs1(u, v, height + 1);
        sz[v] += sz[u];
    }
}
 
void dfs2(int v, int p, int l, int r){
    if (h[v] % 2) x[v] = r--; // mx
    else x[v] = l++; // mn
    for (auto u : adj[v]){
        if (u == p) continue;
        dfs2(u, v, l, l + sz[u] - 1);
        l += sz[u];
    }
}
 
vector<int> label(int n, int k, vector<int> u, vector<int> v){
    // vector<int> BRUH(n); iota(BRUH.begin(), BRUH.end(), 0);
    for (auto &kjsgfh : adj) kjsgfh.clear();
    for (int i = 0; i < n - 1; i++){
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    // cout << endl;
    // for (int i = 0; i < n; i++){
    //     cout << i << ": ";
    //     for (auto u : adj[i]) cout << u << ' ';
    //     cout << endl;
    // }
    dfs1(0, 0, 0);
    // return BRUH;
    dfs2(0, 0, 0, n - 1);
    vector<int> re(n);
    for (int i = 0; i < n; i++) re[i] = x[i];
    // cout << endl;
    // for (int i = 0; i < n; i++) cout << x[i] << ' '; cout << endl;
    // for (int i = 0; i < n; i++) cout << h[i] << ' '; cout << endl;
    return re;
}
 
int find_next_station(int s, int t, vector<int> c){
    // return c[0];
    if (c.size() == 1) return c.front();
    if (s < c[0]){ // x[s] is min, root
        if (t < s || t > c[c.size() - 2]){ // not its children, go up
            return c.back();
        }
        else{ // else, go down, looking for smallest element in c >= t
            int idx = lower_bound(c.begin(), c.end(), t) - c.begin();
            return c[idx];
        }
    }
    else{ // x[s] is max
        if (t > s || t < c[1]) return c.front();
        else{
            int idx = upper_bound(c.begin(), c.end(), t) - c.begin();
            return c[idx - 1];
        }
    }
}

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