oj.uz

Submission #1085690

# Submission time Handle Problem Language Result Execution time Memory
1085690 2024-09-08T15:07:39 Z vladilius Highway Tolls (IOI18_highway) C++17
51 / 100
 145 ms 24104 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) (ask(w) / A);
    assert(dist == (nl / A));
 
    auto cmp = [&](int x, int y){
        return (d[x] < d[y]);
    };
    
    ll BB = 1LL * dist * B;
    
    auto solve = [&](int v, vector<int>& x2, vector<int> vv){
        auto check = [&](int k){
            cl();
            for (int i: x2) w[i] = 1;
            w[x] = 1;
            
            for (int i = 1; i <= k; i++){
                w[pe[vv[i]]] = 1;
            }

            return (ask(w) == BB);
        };
        
        sort(vv.begin(), vv.end(), cmp);

        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));
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 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 2192 KB Output is correct
3 Correct 120 ms 15808 KB Output is correct
4 Correct 113 ms 15824 KB Output is correct
5 Correct 95 ms 15796 KB Output is correct
6 Correct 106 ms 15852 KB Output is correct
7 Correct 115 ms 15800 KB Output is correct
8 Correct 110 ms 15696 KB Output is correct
9 Correct 114 ms 16216 KB Output is correct
10 Correct 105 ms 15804 KB Output is correct
11 Correct 127 ms 16928 KB Output is correct
12 Correct 119 ms 18280 KB Output is correct
13 Correct 123 ms 17108 KB Output is correct
14 Correct 119 ms 17740 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2900 KB Output is correct
2 Correct 18 ms 4980 KB Output is correct
3 Correct 33 ms 7996 KB Output is correct
4 Correct 97 ms 20356 KB Output is correct
5 Correct 88 ms 20852 KB Output is correct
6 Correct 78 ms 23200 KB Output is correct
7 Correct 92 ms 24104 KB Output is correct
8 Correct 98 ms 21120 KB Output is correct
9 Correct 79 ms 22412 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 69 ms 12596 KB Output is correct
4 Correct 117 ms 15816 KB Output is correct
5 Correct 99 ms 15796 KB Output is correct
6 Correct 102 ms 15796 KB Output is correct
7 Correct 95 ms 15800 KB Output is correct
8 Correct 105 ms 15788 KB Output is correct
9 Correct 118 ms 15752 KB Output is correct
10 Correct 111 ms 15800 KB Output is correct
11 Correct 129 ms 16572 KB Output is correct
12 Correct 126 ms 17992 KB Output is correct
13 Correct 145 ms 17164 KB Output is correct
14 Correct 139 ms 17720 KB Output is correct
15 Correct 89 ms 15860 KB Output is correct
16 Correct 98 ms 15804 KB Output is correct
17 Correct 123 ms 17052 KB Output is correct
18 Correct 109 ms 17296 KB Output is correct
19 Correct 107 ms 15804 KB Output is correct
20 Correct 109 ms 18416 KB Output is correct
21 Correct 101 ms 16476 KB Output is correct
22 Correct 82 ms 16460 KB Output is correct
23 Correct 96 ms 16200 KB Output is correct
24 Correct 97 ms 16696 KB Output is correct
25 Correct 118 ms 23496 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 2136 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 2284 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -