oj.uz

Submission #566626

# Submission time Handle Problem Language Result Execution time Memory
566626 2022-05-22T13:16:24 Z hoanghq2004 Highway Tolls (IOI18_highway) C++14
100 / 100
 243 ms 18688 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "highway.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
    vector <vector <pair <int, int>>> g(n), e(n);
    vector <int> ord(n), id(n, -1);
    int m = U.size();
    for (int i = 0; i < m; ++i) {
        g[U[i]].push_back({V[i], i});
        g[V[i]].push_back({U[i], i});
    }
    int L = 0, R = m - 1;
    vector <int> w(m, 0);
    long long tot = ask(w);
    while (L < R) {
        int mid = L + R >> 1;
        vector <int> w(m, 0);
        for (int i = mid + 1; i < m; ++i) w[i] = 1;
        if (ask(w) != tot) L = mid + 1;
        else R = mid;
    }
    int x = L;
    queue <int> q;
    q.push(U[x]);
    q.push(V[x]);
    vector <int> type(n, -1);
    type[U[x]] = 0;
    type[V[x]] = 1;
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (auto [v, i]: g[u]) {
            if (type[v] != -1) continue;
            type[v] = type[u];
            id[v] = i;
            e[u].push_back({v, i});
            q.push(v);
        }
    }
    int ti = 0;
    function <void(int)> dfs = [&](int u) {
        ord[ti++] = u;
        for (auto [v, i]: e[u]) {
            dfs(v);
        }
    };
    dfs(U[x]);
    w.assign(m, -1);
    for (int i = 0; i < n; ++i) {
        if (i == U[x] || i == V[x]) continue;
        w[id[i]] = 0;
    }
    w[x] = 0;
    for (int i = 0; i < m; ++i) if (w[i] == -1) w[i] = 1;
    tot = ask(w);
    L = 0, R = ti - 1;
    while (L < R) {
        int mid = L + R >> 1;
        vector <int> w(m, -1);
        for (int i = 0; i <= mid; ++i) {
            if (ord[i] == U[x] || ord[i] == V[x]) continue;
            if (type[ord[i]] == 0) w[id[ord[i]]] = 0;
        }
        for (int i = 0; i < n; ++i) {
            if (i == U[x] || i == V[x]) continue;
            if (type[i] == 1) w[id[i]] = 0;
        }
        w[x] = 0;
        for (int i = 0; i < m; ++i) if (w[i] == -1) w[i] = 1;
        if (ask(w) == tot) R = mid;
        else L = mid + 1;
    }
    int S = ord[L];
    ti = 0;
    dfs(V[x]);
    L = 0, R = ti - 1;
    while (L < R) {
        int mid = L + R >> 1;
        vector <int> w(m, -1);
        for (int i = 0; i <= mid; ++i) {
            if (ord[i] == U[x] || ord[i] == V[x]) continue;
            if (type[ord[i]] == 1) w[id[ord[i]]] = 0;
        }
        for (int i = 0; i < n; ++i) {
            if (i == U[x] || i == V[x]) continue;
            if (type[i] == 0) w[id[i]] = 0;
        }
        w[x] = 0;
        for (int i = 0; i < m; ++i) if (w[i] == -1) w[i] = 1;
        if (ask(w) == tot) R = mid;
        else L = mid + 1;
    }
    int T = ord[L];
    answer(S, T);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:26:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |         int mid = L + R >> 1;
      |                   ~~^~~
highway.cpp:42:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |         for (auto [v, i]: g[u]) {
      |                   ^
highway.cpp: In lambda function:
highway.cpp:53:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |         for (auto [v, i]: e[u]) {
      |                   ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:68:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |         int mid = L + R >> 1;
      |                   ~~^~~
highway.cpp:88:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |         int mid = L + R >> 1;
      |                   ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 12 ms 1652 KB Output is correct
3 Correct 150 ms 12776 KB Output is correct
4 Correct 136 ms 12768 KB Output is correct
5 Correct 130 ms 12832 KB Output is correct
6 Correct 135 ms 12776 KB Output is correct
7 Correct 140 ms 12836 KB Output is correct
8 Correct 142 ms 12876 KB Output is correct
9 Correct 154 ms 12808 KB Output is correct
10 Correct 114 ms 12956 KB Output is correct
11 Correct 162 ms 14744 KB Output is correct
12 Correct 153 ms 15184 KB Output is correct
13 Correct 133 ms 14736 KB Output is correct
14 Correct 138 ms 15016 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2224 KB Output is correct
2 Correct 23 ms 3988 KB Output is correct
3 Correct 33 ms 6288 KB Output is correct
4 Correct 99 ms 16656 KB Output is correct
5 Correct 97 ms 16868 KB Output is correct
6 Correct 109 ms 18056 KB Output is correct
7 Correct 94 ms 18688 KB Output is correct
8 Correct 114 ms 17036 KB Output is correct
9 Correct 97 ms 17652 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 12 ms 1708 KB Output is correct
3 Correct 94 ms 9952 KB Output is correct
4 Correct 125 ms 12972 KB Output is correct
5 Correct 119 ms 12768 KB Output is correct
6 Correct 132 ms 12768 KB Output is correct
7 Correct 109 ms 12812 KB Output is correct
8 Correct 127 ms 12760 KB Output is correct
9 Correct 174 ms 12940 KB Output is correct
10 Correct 124 ms 12760 KB Output is correct
11 Correct 152 ms 14476 KB Output is correct
12 Correct 164 ms 15100 KB Output is correct
13 Correct 166 ms 14772 KB Output is correct
14 Correct 144 ms 14948 KB Output is correct
15 Correct 107 ms 12764 KB Output is correct
16 Correct 105 ms 12768 KB Output is correct
17 Correct 148 ms 14732 KB Output is correct
18 Correct 134 ms 14968 KB Output is correct
19 Correct 107 ms 12784 KB Output is correct
20 Correct 130 ms 15432 KB Output is correct
21 Correct 97 ms 12608 KB Output is correct
22 Correct 106 ms 12600 KB Output is correct
23 Correct 139 ms 12188 KB Output is correct
24 Correct 148 ms 12692 KB Output is correct
25 Correct 151 ms 18100 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1740 KB Output is correct
2 Correct 16 ms 1756 KB Output is correct
3 Correct 173 ms 13284 KB Output is correct
4 Correct 137 ms 13596 KB Output is correct
5 Correct 243 ms 14528 KB Output is correct
6 Correct 205 ms 14464 KB Output is correct
7 Correct 195 ms 14428 KB Output is correct
8 Correct 218 ms 14524 KB Output is correct
9 Correct 121 ms 8604 KB Output is correct
10 Correct 122 ms 8728 KB Output is correct
11 Correct 152 ms 9824 KB Output is correct
12 Correct 181 ms 12596 KB Output is correct
13 Correct 184 ms 13536 KB Output is correct
14 Correct 212 ms 14596 KB Output is correct
15 Correct 206 ms 14636 KB Output is correct
16 Correct 163 ms 9920 KB Output is correct
17 Correct 126 ms 12456 KB Output is correct
18 Correct 127 ms 12740 KB Output is correct
19 Correct 112 ms 12704 KB Output is correct
20 Correct 114 ms 12720 KB Output is correct
21 Correct 191 ms 14888 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1616 KB Output is correct
2 Correct 15 ms 1724 KB Output is correct
3 Correct 153 ms 13276 KB Output is correct
4 Correct 177 ms 13488 KB Output is correct
5 Correct 178 ms 13612 KB Output is correct
6 Correct 207 ms 14524 KB Output is correct
7 Correct 173 ms 13232 KB Output is correct
8 Correct 191 ms 13476 KB Output is correct
9 Correct 151 ms 13604 KB Output is correct
10 Correct 241 ms 14564 KB Output is correct
11 Correct 219 ms 14428 KB Output is correct
12 Correct 208 ms 14436 KB Output is correct
13 Correct 127 ms 9932 KB Output is correct
14 Correct 118 ms 8832 KB Output is correct
15 Correct 124 ms 9920 KB Output is correct
16 Correct 117 ms 8748 KB Output is correct
17 Correct 130 ms 9824 KB Output is correct
18 Correct 118 ms 8736 KB Output is correct
19 Correct 224 ms 12724 KB Output is correct
20 Correct 219 ms 13584 KB Output is correct
21 Correct 198 ms 14528 KB Output is correct
22 Correct 228 ms 14532 KB Output is correct
23 Correct 225 ms 14524 KB Output is correct
24 Correct 204 ms 14628 KB Output is correct
25 Correct 215 ms 14664 KB Output is correct
26 Correct 196 ms 14536 KB Output is correct
27 Correct 139 ms 12804 KB Output is correct
28 Correct 121 ms 12520 KB Output is correct
29 Correct 114 ms 12996 KB Output is correct
30 Correct 133 ms 12704 KB Output is correct
31 Correct 130 ms 12620 KB Output is correct
32 Correct 142 ms 12548 KB Output is correct
33 Correct 129 ms 12844 KB Output is correct
34 Correct 132 ms 12712 KB Output is correct
35 Correct 97 ms 12564 KB Output is correct
36 Correct 142 ms 12608 KB Output is correct
37 Correct 119 ms 12884 KB Output is correct
38 Correct 127 ms 12684 KB Output is correct
39 Correct 189 ms 15236 KB Output is correct
40 Correct 216 ms 15464 KB Output is correct
41 Correct 240 ms 14880 KB Output is correct
42 Correct 236 ms 14740 KB Output is correct