oj.uz

Submission #744796

# Submission time Handle Problem Language Result Execution time Memory
744796 2023-05-19T05:58:20 Z nguyentunglam Highway Tolls (IOI18_highway) C++17
100 / 100
 257 ms 19744 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
vector<pair<int, int>> adj[N];
vector<int> ke[N];
bool mark[N];
int n, m, par[N], st[N], cnt;
long long init;

void dfs(int u) {
    st[u] = ++cnt;
    for(int &v : ke[u]) dfs(v);
}

int Find(int s) {
    cnt = 0;
    for(int i = 0; i < n; i++) st[i] = 0;
    dfs(s);
//    for(int i = 0; i < n; i++) cout << st[i] << " "; cout << endl;
    int l = 1, r = cnt, ret = 1;
    while (l <= r) {
        int mid = l + r >> 1;
        vector<int> w(m);
        for(int i = 0; i < m; i++) w[i] = mark[i];
        for(int i = 0; i < n; i++) if (st[i] > mid) w[par[i]] = 1;
        if (ask(w) == init) {
            ret = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    for(int i = 0; i < n; i++) if (st[i] == ret) return i;
}
void find_pair(int _n, std::vector<int> u, std::vector<int> v, int a, int b) {
    m = u.size();
    n = _n;
    for(int i = 0; i < n; i++) adj[i].clear(), ke[i].clear();
    for(int i = 0; i < m; i++) {
        adj[u[i]].emplace_back(v[i], i);
        adj[v[i]].emplace_back(u[i], i);
    }

    vector<int> w(m);
    init = ask(w);
    int l = 0, r = m - 1, idx = -1;
    while (l <= r) {
        int mid = l + r >> 1;
        for(int i = 0; i < m; i++) w[i] = 0;
        for(int i = 0; i <= mid; i++) w[i] = 1;
        if (ask(w) > init) idx = mid, r = mid - 1;
        else l = mid + 1;
    }

    for(int i = 0; i < m; i++) mark[i] = 1;
    for(int i = 0; i < n; i++) par[i] = -1;
    mark[idx] = 0;
    par[u[idx]] = par[v[idx]] = idx;
    queue<int> q;
    q.push(u[idx]); q.push(v[idx]);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for(auto &[v, i] : adj[u]) if (par[v] < 0) {
            par[v] = i; mark[i] = 0;
            ke[u].push_back(v);
            q.push(v);
        }
    }
    int res1 = Find(u[idx]), res2 = Find(v[idx]);
    answer(res1, res2);
}

Compilation message

highway.cpp: In function 'int Find(int)':
highway.cpp:23:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |         int mid = l + r >> 1;
      |                   ~~^~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:48:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |         int mid = l + r >> 1;
      |                   ~~^~~
highway.cpp: In function 'int Find(int)':
highway.cpp:34:1: warning: control reaches end of non-void function [-Wreturn-type]
   34 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 5 ms 9716 KB Output is correct
3 Correct 5 ms 9720 KB Output is correct
4 Correct 6 ms 9680 KB Output is correct
5 Correct 5 ms 9680 KB Output is correct
6 Correct 6 ms 9680 KB Output is correct
7 Correct 6 ms 9680 KB Output is correct
8 Correct 6 ms 9680 KB Output is correct
9 Correct 6 ms 9712 KB Output is correct
10 Correct 6 ms 9680 KB Output is correct
11 Correct 7 ms 9680 KB Output is correct
12 Correct 5 ms 9680 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9680 KB Output is correct
2 Correct 16 ms 10540 KB Output is correct
3 Correct 172 ms 17464 KB Output is correct
4 Correct 168 ms 17564 KB Output is correct
5 Correct 144 ms 17456 KB Output is correct
6 Correct 145 ms 17536 KB Output is correct
7 Correct 162 ms 17516 KB Output is correct
8 Correct 127 ms 17460 KB Output is correct
9 Correct 138 ms 17444 KB Output is correct
10 Correct 144 ms 17512 KB Output is correct
11 Correct 147 ms 18624 KB Output is correct
12 Correct 172 ms 18828 KB Output is correct
13 Correct 147 ms 18732 KB Output is correct
14 Correct 165 ms 18660 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 10704 KB Output is correct
2 Correct 38 ms 11872 KB Output is correct
3 Correct 41 ms 13008 KB Output is correct
4 Correct 140 ms 19256 KB Output is correct
5 Correct 97 ms 19220 KB Output is correct
6 Correct 118 ms 19496 KB Output is correct
7 Correct 151 ms 19744 KB Output is correct
8 Correct 117 ms 19412 KB Output is correct
9 Correct 99 ms 19536 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9680 KB Output is correct
2 Correct 18 ms 10448 KB Output is correct
3 Correct 112 ms 15736 KB Output is correct
4 Correct 107 ms 17456 KB Output is correct
5 Correct 130 ms 17460 KB Output is correct
6 Correct 142 ms 17444 KB Output is correct
7 Correct 129 ms 17452 KB Output is correct
8 Correct 115 ms 17448 KB Output is correct
9 Correct 126 ms 17488 KB Output is correct
10 Correct 125 ms 17452 KB Output is correct
11 Correct 128 ms 18576 KB Output is correct
12 Correct 148 ms 18756 KB Output is correct
13 Correct 145 ms 18692 KB Output is correct
14 Correct 140 ms 18668 KB Output is correct
15 Correct 113 ms 17460 KB Output is correct
16 Correct 142 ms 17468 KB Output is correct
17 Correct 166 ms 18592 KB Output is correct
18 Correct 143 ms 18852 KB Output is correct
19 Correct 115 ms 17460 KB Output is correct
20 Correct 165 ms 18836 KB Output is correct
21 Correct 126 ms 17044 KB Output is correct
22 Correct 92 ms 17036 KB Output is correct
23 Correct 142 ms 16908 KB Output is correct
24 Correct 118 ms 17356 KB Output is correct
25 Correct 129 ms 19448 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 10568 KB Output is correct
2 Correct 23 ms 10604 KB Output is correct
3 Correct 166 ms 17956 KB Output is correct
4 Correct 211 ms 18488 KB Output is correct
5 Correct 211 ms 19172 KB Output is correct
6 Correct 257 ms 19180 KB Output is correct
7 Correct 188 ms 19176 KB Output is correct
8 Correct 192 ms 19368 KB Output is correct
9 Correct 119 ms 16264 KB Output is correct
10 Correct 129 ms 16772 KB Output is correct
11 Correct 186 ms 17080 KB Output is correct
12 Correct 229 ms 18376 KB Output is correct
13 Correct 234 ms 18788 KB Output is correct
14 Correct 225 ms 19480 KB Output is correct
15 Correct 243 ms 19488 KB Output is correct
16 Correct 159 ms 17344 KB Output is correct
17 Correct 107 ms 17024 KB Output is correct
18 Correct 111 ms 17400 KB Output is correct
19 Correct 116 ms 17144 KB Output is correct
20 Correct 131 ms 17308 KB Output is correct
21 Correct 234 ms 19580 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 10552 KB Output is correct
2 Correct 17 ms 10600 KB Output is correct
3 Correct 203 ms 18092 KB Output is correct
4 Correct 181 ms 18120 KB Output is correct
5 Correct 156 ms 18348 KB Output is correct
6 Correct 208 ms 19184 KB Output is correct
7 Correct 154 ms 17960 KB Output is correct
8 Correct 163 ms 18188 KB Output is correct
9 Correct 163 ms 18344 KB Output is correct
10 Correct 187 ms 19220 KB Output is correct
11 Correct 191 ms 19180 KB Output is correct
12 Correct 220 ms 19180 KB Output is correct
13 Correct 167 ms 17088 KB Output is correct
14 Correct 192 ms 16728 KB Output is correct
15 Correct 187 ms 17228 KB Output is correct
16 Correct 132 ms 16728 KB Output is correct
17 Correct 153 ms 17080 KB Output is correct
18 Correct 134 ms 16792 KB Output is correct
19 Correct 173 ms 18560 KB Output is correct
20 Correct 176 ms 18984 KB Output is correct
21 Correct 220 ms 19448 KB Output is correct
22 Correct 204 ms 19344 KB Output is correct
23 Correct 212 ms 19372 KB Output is correct
24 Correct 256 ms 19364 KB Output is correct
25 Correct 188 ms 19548 KB Output is correct
26 Correct 195 ms 19480 KB Output is correct
27 Correct 111 ms 17188 KB Output is correct
28 Correct 112 ms 17116 KB Output is correct
29 Correct 100 ms 17460 KB Output is correct
30 Correct 109 ms 17196 KB Output is correct
31 Correct 109 ms 17172 KB Output is correct
32 Correct 115 ms 17076 KB Output is correct
33 Correct 107 ms 17440 KB Output is correct
34 Correct 119 ms 17192 KB Output is correct
35 Correct 106 ms 17132 KB Output is correct
36 Correct 107 ms 16984 KB Output is correct
37 Correct 121 ms 17388 KB Output is correct
38 Correct 107 ms 17220 KB Output is correct
39 Correct 187 ms 19580 KB Output is correct
40 Correct 188 ms 19644 KB Output is correct
41 Correct 186 ms 19448 KB Output is correct
42 Correct 198 ms 19452 KB Output is correct