제출 #305343

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
305343		12tqian	기지국 (IOI20_stations)	C++14	100 / 100	1071 ms	1120 KiB

stations

#ifdef LOCAL
#else
#include "stations.h"
#endif
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#ifdef LOCAL
#define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define dbg(...) 17;
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) { bool f = true; os << "{"; for (const auto &x : c) { if (!f) os << ", "; f = false; os << x; } return os << "}"; }
template<typename T> void debug(string s, T x) { cerr << s << " = " << x << "\n"; }
template<typename T, typename... Args> void debug(string s, T x, Args... args) { cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...); }
#ifdef LOCAL

#else
#endif

int find_next_station(int s, int t, vector<int> c) {
    bool ok = true;
    sort(c.begin(), c.end());
    int sz = c.size();
    if (sz == 1) {
        return c[0];
    }
    for (int i = 0; i < sz; i++) {
        if (t == c[i]) {
            return c[i];
        }
    }
    if (s == 0) {
        for (int i = 0; i < sz; i++) {
            if (t < c[i]) {
                return c[i];
            }
        }
    }
    if (c.back() < s) {
        // vertex is at odd depth
        if (t < c[1] || t > s) {
            return c[0];
        }
        for (int i = sz - 1; i >= 1; i--) {
            if (t > c[i]) {
                return c[i];
            }
        }


    } else {
        if (t > c[sz - 2] || t < s) {
            return c.back();
        }
        for (int i = 0; i < sz - 1; i++) {
            if (t < c[i]) {
                return c[i];
            }
        }
    }
    return -1;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    vector<vector<int>> adj(n);
    for (int i = 0; i < n - 1; i++) {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    vector<int> id(n);
    vector<int> depth(n);
    int cur = 0;
    function<void(int, int)> dfs = [&](int src, int par) {
        if (depth[src] % 2 == 0) {
            id[src] = cur++;
        }
        for (int nxt: adj[src]) {
            if (nxt == par) {
                continue;
            }
            depth[nxt] = depth[src] + 1;
            dfs(nxt, src);
        }
        if (depth[src] % 2 == 1) {
            id[src] = cur++;
        }
    };
    dfs(0, -1);
    return id;
}
#ifdef LOCAL
int main() {
    freopen("file.in", "r", stdin);
//    string line; cin >> line;
    int r;
    cin >> r;
    while (r--) {
        int n, k;
        cin >> n >> k;
        vector<int> u(n);
        vector<int> v(n);
        vector<vector<int>> adj(n);
        for (int i = 0; i < n - 1; i++ ){
            cin >> u[i] >> v[i];
            adj[u[i]].push_back(v[i]);
            adj[v[i]].push_back(u[i]);
        }
        vector<int> id = label(n, k, u, v);
        int q; cin >> q;
        while (q--) {
            int z, y, w;
            cin >> z >> y >> w;
            vector<int> labels;
            for (int nxt: adj[z]) {
                labels.push_back(id[nxt]);
            }
            int v1 = find_next_station(id[z], id[y], labels);
            int v2 = id[w];
            assert(v1 == v2);
        }
    }
    return 0;
}
#else
#endif

컴파일 시 표준 에러 (stderr) 메시지

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:26:10: warning: unused variable 'ok' [-Wunused-variable]
   26 |     bool ok = true;
      |          ^~

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