제출 #679434

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
679434		phoebe	Stations (IOI20_stations)	C++17	0 / 100	1683 ms	2097152 KiB

stations

#include <bits/stdc++.h>
#include "stations.h"
using namespace std;

const int maxn = 1e3 + 10;
int n, sz[maxn] = {0}, h[maxn], x[maxn]; // 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){
    n = N;
    for (int i = 0; i < n; i++){
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    dfs1(1, 1, 0);
    dfs2(1, 1, 0, n - 1);
    vector<int> re(n);
    for (int i = 0; i < n; i++) re[i] = x[i];
    // for (int i = 0; i < n; i++) cout << x[i] << ' '; cout << endl;
    return re;
}

int find_next_station(int s, int t, vector<int> c){
    if (s < c[0]){ // x[s] is min, root
        if (t < s || t > c.back()){ // 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.front()) return c.front();
        else{
            int idx = upper_bound(c.begin(), c.end(), t) - c.begin();
            return c[idx - 1];
        }
    }
}

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