oj.uz

Submission #120381

# Submission time Handle Problem Language Result Execution time Memory
120381 2019-06-24T09:50:51 Z onjo0127 Highway Tolls (IOI18_highway) C++11
90 / 100
 1036 ms 11024 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);
    int P = any(f(any(f(0))));
    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 2424 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 4 ms 2436 KB Output is correct
5 Correct 4 ms 2476 KB Output is correct
6 Correct 4 ms 2348 KB Output is correct
7 Correct 4 ms 2424 KB Output is correct
8 Correct 4 ms 2444 KB Output is correct
9 Correct 4 ms 2424 KB Output is correct
10 Correct 4 ms 2436 KB Output is correct
11 Correct 4 ms 2436 KB Output is correct
12 Correct 4 ms 2424 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2496 KB Output is correct
2 Correct 45 ms 3204 KB Output is correct
3 Correct 635 ms 9268 KB Output is correct
4 Correct 434 ms 9176 KB Output is correct
5 Correct 559 ms 9184 KB Output is correct
6 Correct 342 ms 9176 KB Output is correct
7 Correct 756 ms 9180 KB Output is correct
8 Correct 741 ms 9160 KB Output is correct
9 Correct 717 ms 9164 KB Output is correct
10 Correct 455 ms 9176 KB Output is correct
11 Correct 849 ms 8704 KB Output is correct
12 Correct 730 ms 8708 KB Output is correct
13 Correct 787 ms 8628 KB Output is correct
14 Correct 492 ms 8704 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3088 KB Output is correct
2 Correct 54 ms 3852 KB Output is correct
3 Correct 53 ms 4596 KB Output is correct
4 Correct 183 ms 8612 KB Output is correct
5 Correct 211 ms 8620 KB Output is correct
6 Correct 201 ms 8592 KB Output is correct
7 Correct 175 ms 8632 KB Output is correct
8 Correct 179 ms 8840 KB Output is correct
9 Correct 207 ms 8616 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2528 KB Output is correct
2 Correct 41 ms 3204 KB Output is correct
3 Correct 567 ms 7676 KB Output is correct
4 Correct 782 ms 9168 KB Output is correct
5 Correct 733 ms 9176 KB Output is correct
6 Correct 805 ms 9180 KB Output is correct
7 Correct 762 ms 9292 KB Output is correct
8 Correct 822 ms 9248 KB Output is correct
9 Correct 447 ms 9164 KB Output is correct
10 Correct 709 ms 9296 KB Output is correct
11 Correct 572 ms 8604 KB Output is correct
12 Correct 425 ms 8612 KB Output is correct
13 Correct 497 ms 8612 KB Output is correct
14 Correct 646 ms 8608 KB Output is correct
15 Correct 776 ms 9176 KB Output is correct
16 Correct 671 ms 9268 KB Output is correct
17 Correct 548 ms 8712 KB Output is correct
18 Correct 789 ms 8628 KB Output is correct
19 Correct 810 ms 9196 KB Output is correct
20 Correct 792 ms 8628 KB Output is correct
21 Correct 480 ms 9440 KB Output is correct
22 Correct 325 ms 9576 KB Output is correct
23 Correct 461 ms 9468 KB Output is correct
24 Correct 263 ms 9316 KB Output is correct
25 Correct 300 ms 8724 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3256 KB Output is correct
2 Correct 38 ms 3272 KB Output is correct
3 Correct 553 ms 9536 KB Output is correct
4 Correct 590 ms 10060 KB Output is correct
5 Correct 750 ms 10920 KB Output is correct
6 Correct 620 ms 10936 KB Output is correct
7 Correct 711 ms 11008 KB Output is correct
8 Correct 533 ms 10916 KB Output is correct
9 Correct 344 ms 8892 KB Output is correct
10 Correct 311 ms 9396 KB Output is correct
11 Correct 301 ms 9808 KB Output is correct
12 Correct 658 ms 10512 KB Output is correct
13 Correct 546 ms 10724 KB Output is correct
14 Correct 654 ms 10924 KB Output is correct
15 Correct 543 ms 10908 KB Output is correct
16 Correct 397 ms 10120 KB Output is correct
17 Correct 342 ms 9376 KB Output is correct
18 Correct 259 ms 9664 KB Output is correct
19 Correct 225 ms 9472 KB Output is correct
20 Correct 278 ms 9500 KB Output is correct
21 Correct 1036 ms 10972 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3200 KB Output is correct
2 Correct 21 ms 3308 KB Output is correct
3 Partially correct 708 ms 9560 KB Output is partially correct
4 Partially correct 645 ms 9840 KB Output is partially correct
5 Correct 439 ms 10008 KB Output is correct
6 Partially correct 747 ms 10904 KB Output is partially correct
7 Correct 499 ms 9592 KB Output is correct
8 Partially correct 718 ms 9792 KB Output is partially correct
9 Correct 706 ms 9960 KB Output is correct
10 Partially correct 704 ms 10932 KB Output is partially correct
11 Correct 751 ms 10952 KB Output is correct
12 Partially correct 658 ms 10936 KB Output is partially correct
13 Correct 271 ms 9796 KB Output is correct
14 Correct 355 ms 9396 KB Output is correct
15 Correct 366 ms 9816 KB Output is correct
16 Correct 337 ms 9488 KB Output is correct
17 Correct 336 ms 9824 KB Output is correct
18 Correct 267 ms 9564 KB Output is correct
19 Correct 576 ms 10512 KB Output is correct
20 Correct 755 ms 10728 KB Output is correct
21 Partially correct 813 ms 10908 KB Output is partially correct
22 Partially correct 533 ms 11020 KB Output is partially correct
23 Correct 418 ms 10896 KB Output is correct
24 Partially correct 624 ms 11024 KB Output is partially correct
25 Partially correct 857 ms 10960 KB Output is partially correct
26 Partially correct 898 ms 10944 KB Output is partially correct
27 Partially correct 498 ms 9512 KB Output is partially correct
28 Partially correct 390 ms 9412 KB Output is partially correct
29 Partially correct 410 ms 9784 KB Output is partially correct
30 Correct 412 ms 9532 KB Output is correct
31 Correct 386 ms 9564 KB Output is correct
32 Partially correct 295 ms 9496 KB Output is partially correct
33 Correct 409 ms 9712 KB Output is correct
34 Partially correct 408 ms 9456 KB Output is partially correct
35 Correct 452 ms 9472 KB Output is correct
36 Partially correct 270 ms 9372 KB Output is partially correct
37 Partially correct 296 ms 9668 KB Output is partially correct
38 Correct 333 ms 9608 KB Output is correct
39 Partially correct 883 ms 11000 KB Output is partially correct
40 Partially correct 919 ms 10996 KB Output is partially correct
41 Partially correct 405 ms 10960 KB Output is partially correct
42 Partially correct 852 ms 11012 KB Output is partially correct