oj.uz

Submission #120290

# Submission time Handle Problem Language Result Execution time Memory
120290 2019-06-24T06:48:42 Z 이온조(#2949) Highway Tolls (IOI18_highway) C++14
90 / 100
 1016 ms 11408 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int n, M;
long long ori;
vector<pii> adj[90009];
int D[90009];

int any(vector<int> S) {
    int K = S.size();
    int l = 0, r = K-1;
    while(l <= r) {
        if(l == r) return S[l];
        int m = l+r >> 1;
        vector<int> W(M, 0);
        for(int i=0; i<=m; i++) for(auto& it: adj[S[i]]) W[it.second] = 1;
        if(ask(W) != ori) r = m;
        else l = m+1;
    }
    return S[r+1];
}

vector<int> f(int root) {
    int c = 1;
    for(int i=0; i<n; i++) D[i] = 0;
    queue<int> que; que.push(root); D[root] = 1;
    while(que.size()) {
        int sz = que.size();
        while(sz--) {
            int now; now = que.front(); que.pop();
            for(auto& it: adj[now]) {
                if(!D[it.first]) {
                    D[it.first] = c+1;
                    que.push(it.first);
                }
            }
        }
        ++c;
    }
    vector<int> S;
    for(int i=0; i<n; i++) S.push_back(i);
    sort(S.begin(), S.end(), [&](int P, int Q) {return D[P] > D[Q];});
    return S;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    n = N; M = U.size();
    for(int i=0; i<M; i++) {
        adj[U[i]].push_back({V[i], i});
        adj[V[i]].push_back({U[i], i});
    }
    vector<int> W(M, 0); ori = ask(W);
    vector<int> S = f(0);
    reverse(S.begin(), S.end());
    int P = any(f(any(S)));
    int Q = any(f(P));
    //printf("S: %d, T: %d\n", P, Q);
    answer(P, Q);
}

Compilation message

highway.cpp: In function 'int any(std::vector<int>)':
highway.cpp:16:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = l+r >> 1;
                 ~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 4 ms 2436 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 5 ms 2428 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 4 ms 2344 KB Output is correct
7 Correct 4 ms 2436 KB Output is correct
8 Correct 4 ms 2344 KB Output is correct
9 Correct 4 ms 2552 KB Output is correct
10 Correct 4 ms 2428 KB Output is correct
11 Correct 4 ms 2424 KB Output is correct
12 Correct 4 ms 2440 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2552 KB Output is correct
2 Correct 43 ms 3260 KB Output is correct
3 Correct 602 ms 9644 KB Output is correct
4 Correct 413 ms 9532 KB Output is correct
5 Correct 615 ms 9524 KB Output is correct
6 Correct 305 ms 9524 KB Output is correct
7 Correct 578 ms 9588 KB Output is correct
8 Correct 615 ms 9612 KB Output is correct
9 Correct 505 ms 9568 KB Output is correct
10 Correct 389 ms 9512 KB Output is correct
11 Correct 761 ms 9044 KB Output is correct
12 Correct 611 ms 9040 KB Output is correct
13 Correct 685 ms 9080 KB Output is correct
14 Correct 571 ms 8968 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3064 KB Output is correct
2 Correct 47 ms 3932 KB Output is correct
3 Correct 73 ms 4588 KB Output is correct
4 Correct 229 ms 8952 KB Output is correct
5 Correct 241 ms 8960 KB Output is correct
6 Correct 192 ms 8952 KB Output is correct
7 Correct 225 ms 8988 KB Output is correct
8 Correct 151 ms 8948 KB Output is correct
9 Correct 207 ms 9088 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2492 KB Output is correct
2 Correct 41 ms 3252 KB Output is correct
3 Correct 527 ms 8060 KB Output is correct
4 Correct 685 ms 9536 KB Output is correct
5 Correct 812 ms 9508 KB Output is correct
6 Correct 759 ms 9656 KB Output is correct
7 Correct 912 ms 9644 KB Output is correct
8 Correct 731 ms 9596 KB Output is correct
9 Correct 429 ms 9532 KB Output is correct
10 Correct 642 ms 9584 KB Output is correct
11 Correct 602 ms 8960 KB Output is correct
12 Correct 389 ms 8960 KB Output is correct
13 Correct 525 ms 8972 KB Output is correct
14 Correct 792 ms 9072 KB Output is correct
15 Correct 675 ms 9540 KB Output is correct
16 Correct 760 ms 9644 KB Output is correct
17 Correct 480 ms 8964 KB Output is correct
18 Correct 621 ms 8948 KB Output is correct
19 Correct 685 ms 9648 KB Output is correct
20 Correct 1016 ms 8980 KB Output is correct
21 Correct 400 ms 9828 KB Output is correct
22 Correct 327 ms 9804 KB Output is correct
23 Correct 371 ms 9804 KB Output is correct
24 Correct 269 ms 9748 KB Output is correct
25 Correct 343 ms 9056 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3284 KB Output is correct
2 Correct 36 ms 3320 KB Output is correct
3 Correct 486 ms 9876 KB Output is correct
4 Correct 643 ms 10340 KB Output is correct
5 Correct 631 ms 11296 KB Output is correct
6 Correct 661 ms 11288 KB Output is correct
7 Correct 645 ms 11280 KB Output is correct
8 Correct 438 ms 11276 KB Output is correct
9 Correct 276 ms 9084 KB Output is correct
10 Correct 306 ms 9516 KB Output is correct
11 Correct 353 ms 9996 KB Output is correct
12 Correct 618 ms 10764 KB Output is correct
13 Correct 633 ms 11048 KB Output is correct
14 Correct 757 ms 11388 KB Output is correct
15 Correct 714 ms 11352 KB Output is correct
16 Correct 405 ms 10248 KB Output is correct
17 Correct 405 ms 9788 KB Output is correct
18 Correct 256 ms 10164 KB Output is correct
19 Correct 225 ms 9800 KB Output is correct
20 Correct 297 ms 9848 KB Output is correct
21 Correct 804 ms 11340 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3296 KB Output is correct
2 Correct 32 ms 3324 KB Output is correct
3 Correct 645 ms 10004 KB Output is correct
4 Partially correct 575 ms 10108 KB Output is partially correct
5 Partially correct 597 ms 10332 KB Output is partially correct
6 Partially correct 585 ms 11340 KB Output is partially correct
7 Partially correct 694 ms 10012 KB Output is partially correct
8 Partially correct 673 ms 10084 KB Output is partially correct
9 Partially correct 788 ms 10344 KB Output is partially correct
10 Correct 685 ms 11284 KB Output is correct
11 Correct 791 ms 11288 KB Output is correct
12 Partially correct 812 ms 11388 KB Output is partially correct
13 Correct 282 ms 10012 KB Output is correct
14 Correct 267 ms 9576 KB Output is correct
15 Correct 379 ms 9980 KB Output is correct
16 Correct 326 ms 9704 KB Output is correct
17 Correct 316 ms 9984 KB Output is correct
18 Correct 302 ms 9596 KB Output is correct
19 Correct 503 ms 10812 KB Output is correct
20 Correct 715 ms 11044 KB Output is correct
21 Partially correct 535 ms 11276 KB Output is partially correct
22 Correct 670 ms 11296 KB Output is correct
23 Partially correct 519 ms 11268 KB Output is partially correct
24 Correct 682 ms 11300 KB Output is correct
25 Correct 616 ms 11276 KB Output is correct
26 Partially correct 642 ms 11316 KB Output is partially correct
27 Partially correct 405 ms 9880 KB Output is partially correct
28 Partially correct 325 ms 9784 KB Output is partially correct
29 Partially correct 369 ms 10216 KB Output is partially correct
30 Correct 531 ms 9900 KB Output is correct
31 Correct 487 ms 9872 KB Output is correct
32 Correct 329 ms 9732 KB Output is correct
33 Correct 454 ms 10048 KB Output is correct
34 Partially correct 385 ms 9804 KB Output is partially correct
35 Correct 492 ms 9832 KB Output is correct
36 Partially correct 305 ms 9720 KB Output is partially correct
37 Partially correct 317 ms 10036 KB Output is partially correct
38 Partially correct 344 ms 9980 KB Output is partially correct
39 Correct 857 ms 11408 KB Output is correct
40 Partially correct 783 ms 11396 KB Output is partially correct
41 Partially correct 403 ms 11312 KB Output is partially correct
42 Partially correct 986 ms 11312 KB Output is partially correct