oj.uz

Submission #305343

# Submission time Handle Problem Language Result Execution time Memory
305343 2020-09-23T00:58:17 Z 12tqian Stations (IOI20_stations) C++14
100 / 100
 1071 ms 1120 KB 
#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

Compilation message

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 574 ms 1016 KB Output is correct
2 Correct 493 ms 1024 KB Output is correct
3 Correct 962 ms 640 KB Output is correct
4 Correct 701 ms 640 KB Output is correct
5 Correct 654 ms 640 KB Output is correct
6 Correct 439 ms 1024 KB Output is correct
7 Correct 476 ms 1024 KB Output is correct
8 Correct 1 ms 656 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 804 KB Output is correct
2 Correct 649 ms 956 KB Output is correct
3 Correct 892 ms 776 KB Output is correct
4 Correct 828 ms 640 KB Output is correct
5 Correct 641 ms 640 KB Output is correct
6 Correct 525 ms 824 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 1024 KB Output is correct
2 Correct 453 ms 1024 KB Output is correct
3 Correct 990 ms 896 KB Output is correct
4 Correct 817 ms 804 KB Output is correct
5 Correct 737 ms 768 KB Output is correct
6 Correct 457 ms 1120 KB Output is correct
7 Correct 587 ms 1024 KB Output is correct
8 Correct 3 ms 692 KB Output is correct
9 Correct 5 ms 656 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 646 ms 640 KB Output is correct
12 Correct 555 ms 1008 KB Output is correct
13 Correct 488 ms 992 KB Output is correct
14 Correct 580 ms 828 KB Output is correct
15 Correct 67 ms 800 KB Output is correct
16 Correct 87 ms 768 KB Output is correct
17 Correct 110 ms 768 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1071 ms 640 KB Output is correct
2 Correct 713 ms 648 KB Output is correct
3 Correct 688 ms 640 KB Output is correct
4 Correct 3 ms 768 KB Output is correct
5 Correct 4 ms 644 KB Output is correct
6 Correct 0 ms 640 KB Output is correct
7 Correct 668 ms 900 KB Output is correct
8 Correct 926 ms 644 KB Output is correct
9 Correct 830 ms 648 KB Output is correct
10 Correct 652 ms 880 KB Output is correct
11 Correct 7 ms 640 KB Output is correct
12 Correct 6 ms 640 KB Output is correct
13 Correct 6 ms 652 KB Output is correct
14 Correct 4 ms 640 KB Output is correct
15 Correct 1 ms 640 KB Output is correct
16 Correct 530 ms 640 KB Output is correct
17 Correct 508 ms 640 KB Output is correct
18 Correct 538 ms 644 KB Output is correct
19 Correct 565 ms 640 KB Output is correct
20 Correct 543 ms 652 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 650 ms 1008 KB Output is correct
2 Correct 592 ms 1008 KB Output is correct
3 Correct 953 ms 776 KB Output is correct
4 Correct 825 ms 776 KB Output is correct
5 Correct 666 ms 784 KB Output is correct
6 Correct 494 ms 1008 KB Output is correct
7 Correct 487 ms 776 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Correct 3 ms 652 KB Output is correct
10 Correct 1 ms 652 KB Output is correct
11 Correct 545 ms 768 KB Output is correct
12 Correct 594 ms 808 KB Output is correct
13 Correct 1055 ms 640 KB Output is correct
14 Correct 720 ms 792 KB Output is correct
15 Correct 697 ms 648 KB Output is correct
16 Correct 504 ms 836 KB Output is correct
17 Correct 780 ms 640 KB Output is correct
18 Correct 567 ms 1008 KB Output is correct
19 Correct 501 ms 1024 KB Output is correct
20 Correct 491 ms 832 KB Output is correct
21 Correct 58 ms 892 KB Output is correct
22 Correct 86 ms 852 KB Output is correct
23 Correct 109 ms 820 KB Output is correct
24 Correct 5 ms 644 KB Output is correct
25 Correct 4 ms 640 KB Output is correct
26 Correct 5 ms 648 KB Output is correct
27 Correct 4 ms 640 KB Output is correct
28 Correct 2 ms 644 KB Output is correct
29 Correct 568 ms 784 KB Output is correct
30 Correct 560 ms 648 KB Output is correct
31 Correct 584 ms 768 KB Output is correct
32 Correct 595 ms 644 KB Output is correct
33 Correct 518 ms 652 KB Output is correct
34 Correct 343 ms 1024 KB Output is correct
35 Correct 467 ms 1008 KB Output is correct
36 Correct 555 ms 1112 KB Output is correct
37 Correct 514 ms 1008 KB Output is correct
38 Correct 560 ms 920 KB Output is correct
39 Correct 512 ms 768 KB Output is correct
40 Correct 570 ms 792 KB Output is correct
41 Correct 508 ms 760 KB Output is correct
42 Correct 69 ms 844 KB Output is correct
43 Correct 109 ms 820 KB Output is correct
44 Correct 128 ms 832 KB Output is correct
45 Correct 224 ms 768 KB Output is correct
46 Correct 357 ms 768 KB Output is correct
47 Correct 322 ms 780 KB Output is correct
48 Correct 70 ms 768 KB Output is correct
49 Correct 61 ms 824 KB Output is correct