oj.uz

Submission #120397

# Submission time Handle Problem Language Result Execution time Memory
120397 2019-06-24T11:02:32 Z onjo0127 Highway Tolls (IOI18_highway) C++11
100 / 100
 594 ms 12456 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];
vector<int> u, v;
int D[90009];

pii ebs() {
    int l = 0, r = M-1;
    while(l <= r) {
        if(l == r) return (pii){u[l], v[l]};
        int m = l+r >> 1;
        vector<int> W(M, 0);
        for(int i=0; i<=m; i++) W[i] = 1;
        if(ask(W) != ori) r = m;
        else l = m+1;
    }
    return (pii){u[r+1], v[r+1]};
}

int vbs(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(vector<int>& D, 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) {
    u = U; v = V;
    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 al, be; tie(al, be) = ebs();
    vector<int> DA(N), DB(N);
    f(DA, al); f(DB, be);
    vector<int> AS, BS, CS;
    for(int i=0; i<N; i++) {
        if(DA[i] < DB[i]) AS.push_back(i);
        else BS.push_back(i);
    }
    sort(AS.begin(), AS.end(), [&](int X, int Y) {return DA[X] > DA[Y];});
    int P = vbs(AS);
    for(auto& it: BS) if(DB[it] == (ori / A) - DA[P] + 1) CS.push_back(it);
    sort(CS.begin(), CS.end(), [&](int X, int Y) {return DB[X] > DB[Y];});
    int Q = vbs(CS);
    answer(P, Q);
}

Compilation message

highway.cpp: In function 'pii ebs()':
highway.cpp:16:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = l+r >> 1;
                 ~^~
highway.cpp: In function 'int vbs(std::vector<int>)':
highway.cpp:30: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 2372 KB Output is correct
3 Correct 4 ms 2340 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 4 ms 2424 KB Output is correct
7 Correct 4 ms 2424 KB Output is correct
8 Correct 4 ms 2344 KB Output is correct
9 Correct 4 ms 2344 KB Output is correct
10 Correct 5 ms 2424 KB Output is correct
11 Correct 4 ms 2344 KB Output is correct
12 Correct 4 ms 2332 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 30 ms 3284 KB Output is correct
3 Correct 358 ms 10220 KB Output is correct
4 Correct 199 ms 9876 KB Output is correct
5 Correct 230 ms 9872 KB Output is correct
6 Correct 149 ms 9880 KB Output is correct
7 Correct 278 ms 9856 KB Output is correct
8 Correct 183 ms 9872 KB Output is correct
9 Correct 386 ms 10236 KB Output is correct
10 Correct 186 ms 9884 KB Output is correct
11 Correct 343 ms 9508 KB Output is correct
12 Correct 375 ms 9888 KB Output is correct
13 Correct 170 ms 9292 KB Output is correct
14 Correct 395 ms 9644 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3216 KB Output is correct
2 Correct 41 ms 3944 KB Output is correct
3 Correct 53 ms 4904 KB Output is correct
4 Correct 168 ms 9540 KB Output is correct
5 Correct 212 ms 9420 KB Output is correct
6 Correct 132 ms 9336 KB Output is correct
7 Correct 208 ms 9656 KB Output is correct
8 Correct 164 ms 9420 KB Output is correct
9 Correct 163 ms 9840 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2552 KB Output is correct
2 Correct 25 ms 3256 KB Output is correct
3 Correct 156 ms 8304 KB Output is correct
4 Correct 181 ms 9880 KB Output is correct
5 Correct 594 ms 10332 KB Output is correct
6 Correct 154 ms 9976 KB Output is correct
7 Correct 370 ms 10292 KB Output is correct
8 Correct 396 ms 10228 KB Output is correct
9 Correct 387 ms 10308 KB Output is correct
10 Correct 390 ms 10288 KB Output is correct
11 Correct 354 ms 9652 KB Output is correct
12 Correct 244 ms 9280 KB Output is correct
13 Correct 335 ms 9872 KB Output is correct
14 Correct 420 ms 9568 KB Output is correct
15 Correct 160 ms 9988 KB Output is correct
16 Correct 183 ms 9852 KB Output is correct
17 Correct 331 ms 9644 KB Output is correct
18 Correct 522 ms 9756 KB Output is correct
19 Correct 382 ms 10236 KB Output is correct
20 Correct 208 ms 9280 KB Output is correct
21 Correct 290 ms 10732 KB Output is correct
22 Correct 196 ms 10376 KB Output is correct
23 Correct 299 ms 10664 KB Output is correct
24 Correct 277 ms 10392 KB Output is correct
25 Correct 260 ms 9848 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3320 KB Output is correct
2 Correct 36 ms 3360 KB Output is correct
3 Correct 223 ms 10676 KB Output is correct
4 Correct 318 ms 11176 KB Output is correct
5 Correct 274 ms 12408 KB Output is correct
6 Correct 317 ms 12456 KB Output is correct
7 Correct 337 ms 12336 KB Output is correct
8 Correct 301 ms 12216 KB Output is correct
9 Correct 271 ms 9876 KB Output is correct
10 Correct 200 ms 10384 KB Output is correct
11 Correct 241 ms 10776 KB Output is correct
12 Correct 365 ms 11672 KB Output is correct
13 Correct 354 ms 11892 KB Output is correct
14 Correct 426 ms 12084 KB Output is correct
15 Correct 450 ms 12332 KB Output is correct
16 Correct 256 ms 10940 KB Output is correct
17 Correct 271 ms 10516 KB Output is correct
18 Correct 165 ms 11224 KB Output is correct
19 Correct 207 ms 10524 KB Output is correct
20 Correct 177 ms 11176 KB Output is correct
21 Correct 310 ms 12452 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 3300 KB Output is correct
2 Correct 55 ms 3356 KB Output is correct
3 Correct 285 ms 10376 KB Output is correct
4 Correct 260 ms 10880 KB Output is correct
5 Correct 299 ms 11196 KB Output is correct
6 Correct 263 ms 12248 KB Output is correct
7 Correct 268 ms 10796 KB Output is correct
8 Correct 266 ms 10528 KB Output is correct
9 Correct 339 ms 11192 KB Output is correct
10 Correct 353 ms 12312 KB Output is correct
11 Correct 373 ms 12340 KB Output is correct
12 Correct 431 ms 12348 KB Output is correct
13 Correct 269 ms 10736 KB Output is correct
14 Correct 280 ms 10384 KB Output is correct
15 Correct 206 ms 10736 KB Output is correct
16 Correct 239 ms 10388 KB Output is correct
17 Correct 213 ms 11072 KB Output is correct
18 Correct 297 ms 10576 KB Output is correct
19 Correct 315 ms 11644 KB Output is correct
20 Correct 374 ms 12152 KB Output is correct
21 Correct 331 ms 12064 KB Output is correct
22 Correct 326 ms 12048 KB Output is correct
23 Correct 372 ms 12312 KB Output is correct
24 Correct 349 ms 12264 KB Output is correct
25 Correct 439 ms 12272 KB Output is correct
26 Correct 428 ms 12340 KB Output is correct
27 Correct 293 ms 10560 KB Output is correct
28 Correct 292 ms 11164 KB Output is correct
29 Correct 333 ms 10908 KB Output is correct
30 Correct 225 ms 10644 KB Output is correct
31 Correct 294 ms 10704 KB Output is correct
32 Correct 235 ms 10464 KB Output is correct
33 Correct 286 ms 11448 KB Output is correct
34 Correct 190 ms 10624 KB Output is correct
35 Correct 310 ms 10524 KB Output is correct
36 Correct 207 ms 11076 KB Output is correct
37 Correct 213 ms 10768 KB Output is correct
38 Correct 243 ms 10972 KB Output is correct
39 Correct 398 ms 12432 KB Output is correct
40 Correct 442 ms 12452 KB Output is correct
41 Correct 202 ms 11972 KB Output is correct
42 Correct 474 ms 12416 KB Output is correct