oj.uz

Submission #156492

# Submission time Handle Problem Language Result Execution time Memory
156492 2019-10-06T08:18:46 Z rama_pang Highway Tolls (IOI18_highway) C++14
100 / 100
 362 ms 10776 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
 
lint N, M, A, B;
vector<vector<pair<int, int>>> G;
vector<int> LC, RC, color;
int S, T;

void find_pair(int _N, vector<int> U, vector<int> V, int _A, int _B) {
    N = _N, A = _A, B = _B, M = U.size(); G.resize(N);
    for (int i = 0; i < M; i++) {
        G[U[i]].emplace_back(V[i], i);
        G[V[i]].emplace_back(U[i], i);
    }
    vector<int> guess(M, 0);
    lint D = ask(guess);
    lint le, ri, ans, check;
    /* find and edge e = uv, then construct tree rooted from u and from v */
    le = 0, ri = M - 1;
    while (le < ri) {
        lint mid = (le + ri) / 2;
        for (int i = 0; i < M; i++) guess[i] = i <= mid;
        if (ask(guess) != D) {
            ri = mid;                
        } else {
            le = mid + 1;
        }
    }
    ans = le;
    /* construct BFS tree */
    queue<int> q; q.push(U[ans]), q.push(V[ans]);
    color.assign(N, 0);
    color[U[ans]] = 1; color[V[ans]] = 2;
    LC.push_back(U[ans]); RC.push_back(V[ans]);

    while (!q.empty()) {
        int f = q.front(); q.pop();
        for (auto &g : G[f])  {
            int v = g.first, id = g.second;
            if (color[v] == 0) {
                if (color[f] == 1) LC.push_back(v);
                if (color[f] == 2) RC.push_back(v);
                color[v] = color[f];
                q.push(v);
            }
        }
    }
    /* binary search the answer */
    auto get = [&](vector<int> E) {
        le = 0, ri = E.size() - 1;
        while (le < ri) {
            int mid = (le + ri) / 2;
            vector<bool> cur(N);
            for (int i = mid + 1; i < E.size(); i++) {
                cur[E[i]] = true;
            }
            for (int i = 0; i < M; i++) {
                guess[i] = cur[U[i]] || cur[V[i]];
            }
            if (ask(guess) != D) {
                le = mid + 1;
            } else {
                ri = mid;
            }
        }
        return E[le];
    };
    
    answer(get(LC), get(RC));
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:41:30: warning: unused variable 'id' [-Wunused-variable]
             int v = g.first, id = g.second;
                              ^~
highway.cpp: In lambda function:
highway.cpp:56:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = mid + 1; i < E.size(); i++) {
                                   ~~^~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:19:23: warning: unused variable 'check' [-Wunused-variable]
     lint le, ri, ans, check;
                       ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 408 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 320 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 412 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 248 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 248 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 45 ms 1204 KB Output is correct
3 Correct 203 ms 8884 KB Output is correct
4 Correct 205 ms 8808 KB Output is correct
5 Correct 210 ms 8876 KB Output is correct
6 Correct 196 ms 8820 KB Output is correct
7 Correct 212 ms 8824 KB Output is correct
8 Correct 207 ms 8888 KB Output is correct
9 Correct 202 ms 8900 KB Output is correct
10 Correct 207 ms 8808 KB Output is correct
11 Correct 241 ms 8244 KB Output is correct
12 Correct 207 ms 8188 KB Output is correct
13 Correct 202 ms 8208 KB Output is correct
14 Correct 218 ms 8376 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1272 KB Output is correct
2 Correct 41 ms 2112 KB Output is correct
3 Correct 81 ms 2936 KB Output is correct
4 Correct 179 ms 8232 KB Output is correct
5 Correct 164 ms 8112 KB Output is correct
6 Correct 173 ms 8200 KB Output is correct
7 Correct 185 ms 8328 KB Output is correct
8 Correct 177 ms 8300 KB Output is correct
9 Correct 184 ms 8204 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 41 ms 1288 KB Output is correct
3 Correct 158 ms 7036 KB Output is correct
4 Correct 207 ms 8920 KB Output is correct
5 Correct 198 ms 8900 KB Output is correct
6 Correct 218 ms 8872 KB Output is correct
7 Correct 219 ms 8832 KB Output is correct
8 Correct 197 ms 8796 KB Output is correct
9 Correct 239 ms 8764 KB Output is correct
10 Correct 220 ms 8808 KB Output is correct
11 Correct 225 ms 8228 KB Output is correct
12 Correct 231 ms 8192 KB Output is correct
13 Correct 211 ms 8160 KB Output is correct
14 Correct 217 ms 8240 KB Output is correct
15 Correct 208 ms 8852 KB Output is correct
16 Correct 167 ms 8928 KB Output is correct
17 Correct 233 ms 8400 KB Output is correct
18 Correct 208 ms 8236 KB Output is correct
19 Correct 201 ms 8904 KB Output is correct
20 Correct 220 ms 8264 KB Output is correct
21 Correct 177 ms 9444 KB Output is correct
22 Correct 173 ms 9344 KB Output is correct
23 Correct 195 ms 9280 KB Output is correct
24 Correct 195 ms 9348 KB Output is correct
25 Correct 207 ms 8288 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1388 KB Output is correct
2 Correct 27 ms 1420 KB Output is correct
3 Correct 212 ms 9288 KB Output is correct
4 Correct 258 ms 9648 KB Output is correct
5 Correct 315 ms 10564 KB Output is correct
6 Correct 318 ms 10584 KB Output is correct
7 Correct 352 ms 10620 KB Output is correct
8 Correct 318 ms 10652 KB Output is correct
9 Correct 273 ms 7004 KB Output is correct
10 Correct 277 ms 7320 KB Output is correct
11 Correct 261 ms 8156 KB Output is correct
12 Correct 308 ms 9736 KB Output is correct
13 Correct 344 ms 10288 KB Output is correct
14 Correct 314 ms 10684 KB Output is correct
15 Correct 303 ms 10596 KB Output is correct
16 Correct 268 ms 8260 KB Output is correct
17 Correct 205 ms 9216 KB Output is correct
18 Correct 202 ms 9452 KB Output is correct
19 Correct 194 ms 9284 KB Output is correct
20 Correct 210 ms 9456 KB Output is correct
21 Correct 298 ms 10556 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1192 KB Output is correct
2 Correct 22 ms 1456 KB Output is correct
3 Correct 266 ms 9244 KB Output is correct
4 Correct 269 ms 9280 KB Output is correct
5 Correct 288 ms 9584 KB Output is correct
6 Correct 324 ms 10520 KB Output is correct
7 Correct 226 ms 9220 KB Output is correct
8 Correct 253 ms 9292 KB Output is correct
9 Correct 281 ms 9616 KB Output is correct
10 Correct 362 ms 10596 KB Output is correct
11 Correct 323 ms 10488 KB Output is correct
12 Correct 274 ms 10560 KB Output is correct
13 Correct 287 ms 8080 KB Output is correct
14 Correct 261 ms 7304 KB Output is correct
15 Correct 270 ms 8088 KB Output is correct
16 Correct 274 ms 7300 KB Output is correct
17 Correct 272 ms 8072 KB Output is correct
18 Correct 261 ms 7396 KB Output is correct
19 Correct 324 ms 9724 KB Output is correct
20 Correct 290 ms 10124 KB Output is correct
21 Correct 336 ms 10776 KB Output is correct
22 Correct 331 ms 10584 KB Output is correct
23 Correct 330 ms 10600 KB Output is correct
24 Correct 321 ms 10632 KB Output is correct
25 Correct 321 ms 10568 KB Output is correct
26 Correct 321 ms 10684 KB Output is correct
27 Correct 206 ms 9344 KB Output is correct
28 Correct 197 ms 9380 KB Output is correct
29 Correct 202 ms 9616 KB Output is correct
30 Correct 192 ms 9448 KB Output is correct
31 Correct 208 ms 9364 KB Output is correct
32 Correct 206 ms 9432 KB Output is correct
33 Correct 204 ms 9544 KB Output is correct
34 Correct 206 ms 9404 KB Output is correct
35 Correct 199 ms 9404 KB Output is correct
36 Correct 212 ms 9212 KB Output is correct
37 Correct 209 ms 9532 KB Output is correct
38 Correct 202 ms 9456 KB Output is correct
39 Correct 312 ms 10772 KB Output is correct
40 Correct 298 ms 10676 KB Output is correct
41 Correct 292 ms 10592 KB Output is correct
42 Correct 314 ms 10696 KB Output is correct