oj.uz

Submission #1085719

# Submission time Handle Problem Language Result Execution time Memory
1085719 2024-09-08T15:36:19 Z vladilius Highway Tolls (IOI18_highway) C++17
100 / 100
 175 ms 24100 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

void find_pair(int n, vector<int> U, vector<int> V, int A, int B){
    int m = (int) U.size();
    vector<pii> g[n + 1];
    for (int i = 0; i < m; i++){
        U[i]++; V[i]++;
        g[U[i]].pb({V[i], i});
        g[V[i]].pb({U[i], i});
    }
    
    vector<int> w(m);
    ll nl = ask(w);
    
    auto check1 = [&](int x){
        fill(w.begin(), w.end(), 0);
        for (int i = x + 1; i < m; i++) w[i] = 1;
        return (ask(w) == nl);
    };
    
    int l = 0, r = m - 1;
    while (l + 1 < r){
        int k = (l + r) / 2;
        if (check1(k)){
            r = k;
        }
        else {
            l = k + 1;
        }
    }
    if (check1(l)) r = l;
    
    int x = r;

    vector<bool> used(n + 1);
    vector<int> ed = {x};
    queue<int> q({V[x], U[x]});
    used[V[x]] = used[U[x]] = 1;
    while (!q.empty()){
        int f = q.front(); q.pop();
        for (auto [i, j]: g[f]){
            if (used[i]) continue;
            used[i] = 1;
            q.push(i);
            ed.pb(j);
        }
    }
    
    auto cl = [&](){
        fill(w.begin(), w.end(), 1);
        for (int i: ed) w[i] = 0;
    };
    
    cl();
    vector<pii> t[n + 1];
    for (int i: ed){
        t[U[i]].pb({V[i], i});
        t[V[i]].pb({U[i], i});
    }
    
    vector<int> d(n + 1), p(n + 1), pe(n + 1);
    function<void(int, int, vector<int>&, vector<int>&)> dfs = [&](int v, int pr, vector<int>& E, vector<int>& q){
        q.pb(v);
        p[v] = pr;
        for (auto [i, j]: t[v]){
            if (i == pr || j == x) continue;
            d[i] = d[v] + 1;
            pe[i] = j;
            E.pb(j);
            dfs(i, v, E, q);
        }
    };
    
    vector<int> d1, d2, t1, t2;
    dfs(U[x], 0, d1, t1);
    dfs(V[x], 0, d2, t2);
    
    int dist = (int) (nl / A);
 
    auto cmp = [&](int x, int y){
        return (d[x] < d[y]);
    };
    
    ll AA = 1LL * dist * A;
    
    auto solve = [&](int v, vector<int>& x2, vector<int> vv){
        auto check = [&](int k){
            fill(w.begin(), w.end(), 1);
            for (int i: x2) w[i] = 0;
            w[x] = 0;
            
            for (int i = 1; i <= k; i++){
                w[pe[vv[i]]] = 0;
            }

            return (ask(w) == AA);
        };

        int l = 0, r = (int) vv.size() - 1;
        while (l + 1 < r){
            int k = (l + r) / 2;
            if (check(k)){
                r = k;
            }
            else {
                l = k + 1;
            }
        }
        if (check(l)) r = l;
        
        return (vv[r] - 1);
    };
    
    answer(solve(U[x], d2, t1), solve(V[x], d1, t2));
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:87:10: warning: variable 'cmp' set but not used [-Wunused-but-set-variable]
   87 |     auto cmp = [&](int x, int y){
      |          ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 596 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 12 ms 2040 KB Output is correct
3 Correct 96 ms 15824 KB Output is correct
4 Correct 107 ms 15804 KB Output is correct
5 Correct 105 ms 15892 KB Output is correct
6 Correct 101 ms 15760 KB Output is correct
7 Correct 93 ms 15804 KB Output is correct
8 Correct 92 ms 15944 KB Output is correct
9 Correct 105 ms 16088 KB Output is correct
10 Correct 86 ms 15812 KB Output is correct
11 Correct 113 ms 16924 KB Output is correct
12 Correct 109 ms 18216 KB Output is correct
13 Correct 95 ms 17180 KB Output is correct
14 Correct 102 ms 17484 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2816 KB Output is correct
2 Correct 18 ms 4960 KB Output is correct
3 Correct 26 ms 8016 KB Output is correct
4 Correct 84 ms 20352 KB Output is correct
5 Correct 77 ms 20844 KB Output is correct
6 Correct 83 ms 23232 KB Output is correct
7 Correct 80 ms 24100 KB Output is correct
8 Correct 84 ms 21104 KB Output is correct
9 Correct 95 ms 22416 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 10 ms 2136 KB Output is correct
3 Correct 72 ms 12512 KB Output is correct
4 Correct 98 ms 15820 KB Output is correct
5 Correct 92 ms 16576 KB Output is correct
6 Correct 92 ms 15788 KB Output is correct
7 Correct 85 ms 15808 KB Output is correct
8 Correct 92 ms 15752 KB Output is correct
9 Correct 109 ms 15752 KB Output is correct
10 Correct 101 ms 15816 KB Output is correct
11 Correct 109 ms 16572 KB Output is correct
12 Correct 126 ms 17984 KB Output is correct
13 Correct 116 ms 17404 KB Output is correct
14 Correct 109 ms 17496 KB Output is correct
15 Correct 92 ms 15804 KB Output is correct
16 Correct 86 ms 15820 KB Output is correct
17 Correct 115 ms 17048 KB Output is correct
18 Correct 103 ms 17280 KB Output is correct
19 Correct 90 ms 15808 KB Output is correct
20 Correct 102 ms 18268 KB Output is correct
21 Correct 81 ms 16448 KB Output is correct
22 Correct 79 ms 16468 KB Output is correct
23 Correct 88 ms 16056 KB Output is correct
24 Correct 94 ms 16620 KB Output is correct
25 Correct 111 ms 23476 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2136 KB Output is correct
2 Correct 12 ms 2212 KB Output is correct
3 Correct 111 ms 16352 KB Output is correct
4 Correct 120 ms 16472 KB Output is correct
5 Correct 152 ms 17832 KB Output is correct
6 Correct 149 ms 17312 KB Output is correct
7 Correct 151 ms 17272 KB Output is correct
8 Correct 157 ms 17704 KB Output is correct
9 Correct 109 ms 9416 KB Output is correct
10 Correct 93 ms 9276 KB Output is correct
11 Correct 123 ms 11524 KB Output is correct
12 Correct 136 ms 14892 KB Output is correct
13 Correct 140 ms 15972 KB Output is correct
14 Correct 149 ms 17308 KB Output is correct
15 Correct 145 ms 17016 KB Output is correct
16 Correct 118 ms 11080 KB Output is correct
17 Correct 98 ms 16332 KB Output is correct
18 Correct 96 ms 16560 KB Output is correct
19 Correct 100 ms 16676 KB Output is correct
20 Correct 103 ms 16652 KB Output is correct
21 Correct 137 ms 17988 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2136 KB Output is correct
2 Correct 11 ms 2136 KB Output is correct
3 Correct 100 ms 16160 KB Output is correct
4 Correct 117 ms 16584 KB Output is correct
5 Correct 128 ms 16660 KB Output is correct
6 Correct 175 ms 17420 KB Output is correct
7 Correct 116 ms 16128 KB Output is correct
8 Correct 114 ms 16248 KB Output is correct
9 Correct 117 ms 16472 KB Output is correct
10 Correct 135 ms 17196 KB Output is correct
11 Correct 150 ms 17228 KB Output is correct
12 Correct 149 ms 17416 KB Output is correct
13 Correct 109 ms 11328 KB Output is correct
14 Correct 99 ms 9276 KB Output is correct
15 Correct 107 ms 11312 KB Output is correct
16 Correct 99 ms 9280 KB Output is correct
17 Correct 122 ms 11328 KB Output is correct
18 Correct 98 ms 9416 KB Output is correct
19 Correct 163 ms 14852 KB Output is correct
20 Correct 148 ms 16068 KB Output is correct
21 Correct 152 ms 17056 KB Output is correct
22 Correct 156 ms 16988 KB Output is correct
23 Correct 147 ms 17000 KB Output is correct
24 Correct 143 ms 17252 KB Output is correct
25 Correct 152 ms 17296 KB Output is correct
26 Correct 153 ms 17080 KB Output is correct
27 Correct 93 ms 16812 KB Output is correct
28 Correct 90 ms 16200 KB Output is correct
29 Correct 94 ms 16564 KB Output is correct
30 Correct 107 ms 16364 KB Output is correct
31 Correct 98 ms 16372 KB Output is correct
32 Correct 95 ms 16276 KB Output is correct
33 Correct 111 ms 16516 KB Output is correct
34 Correct 113 ms 16524 KB Output is correct
35 Correct 91 ms 16368 KB Output is correct
36 Correct 90 ms 16092 KB Output is correct
37 Correct 93 ms 16576 KB Output is correct
38 Correct 105 ms 16976 KB Output is correct
39 Correct 139 ms 18548 KB Output is correct
40 Correct 149 ms 19480 KB Output is correct
41 Correct 164 ms 17788 KB Output is correct
42 Correct 143 ms 17476 KB Output is correct