oj.uz

Submission #1081757

# Submission time Handle Problem Language Result Execution time Memory
1081757 2024-08-30T10:08:18 Z vladilius Highway Tolls (IOI18_highway) C++17
51 / 100
 142 ms 24376 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);
    vector<int> all;
    for (int i = 0; i < m; i++) all.pb(i);
    
    while (all.size() > 1){
        int k = (int) all.size() / 2;
        fill(w.begin(), w.end(), 0);
        for (int i = 0; i < k; i++) w[all[i]] = 1;
        
        if (ask(w) == nl){
            reverse(all.begin(), all.end());
            k = (int) all.size() - k;
            while (all.size() > k) all.pop_back();
        }
        else {
            while (all.size() > k) all.pop_back();
        }
    }
    
    int x = all[0];
    
    vector<bool> used(n + 1);
    vector<int> ed = {x};
    queue<int> q;
    q.push(V[x]);
    q.push(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] || j == x) continue;
            used[i] = 1;
            q.push(i);
            ed.pb(j);
        }
    }
    
    fill(w.begin(), w.end(), 1);
    
    auto cl = [&](){
        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>& ed, 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;
            ed.pb(j);
            dfs(i, v, ed, 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);
    
    auto add = [&](int x, int y){
        while (y != x && !w[pe[y]]){
            w[pe[y]] = 1;
            y = p[y];
        }
    };
    
    auto solve = [&](int v, vector<int>& x1, vector<int>& x2, vector<int>& vv){
        cl();
        for (int i: x2) w[i] = 1;
        int ds = (int) ((ask(w) + B - A - 1LL * dist * B) / (A - B));
        
        vector<int> all;
        for (int i: vv){
            if (d[i] == ds){
                all.pb(i);
            }
        }
        
        while (all.size() > 1){
            int k = (int) all.size() / 2;
            cl();
            for (int i = 0; i < k; i++){
                add(v, all[i]);
            }
            ll sm = ask(w);
            if (sm == (1LL * A * (dist - ds) + 1LL * B * ds)){
                while (all.size() > k){
                    all.pop_back();
                }
            }
            else {
                reverse(all.begin(), all.end());
                k = (int) all.size() - k;
                while (all.size() > k) all.pop_back();
            }
        }
        
        return (all[0] - 1);
    };
    
    answer(solve(U[x], d1, d2, t1), solve(V[x], d2, d1, t2));
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:33:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |             while (all.size() > k) all.pop_back();
      |                    ~~~~~~~~~~~^~~
highway.cpp:36:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |             while (all.size() > k) all.pop_back();
      |                    ~~~~~~~~~~~^~~
highway.cpp: In lambda function:
highway.cpp:117:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  117 |                 while (all.size() > k){
      |                        ~~~~~~~~~~~^~~
highway.cpp:124:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  124 |                 while (all.size() > k) all.pop_back();
      |                        ~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 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 512 KB Output is correct
11 Correct 0 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 1 ms 600 KB Output is correct
2 Correct 10 ms 2136 KB Output is correct
3 Correct 107 ms 15980 KB Output is correct
4 Correct 101 ms 16032 KB Output is correct
5 Correct 94 ms 16012 KB Output is correct
6 Correct 94 ms 15976 KB Output is correct
7 Correct 95 ms 15980 KB Output is correct
8 Correct 105 ms 15972 KB Output is correct
9 Correct 94 ms 16216 KB Output is correct
10 Correct 93 ms 15984 KB Output is correct
11 Correct 95 ms 16960 KB Output is correct
12 Correct 106 ms 18168 KB Output is correct
13 Correct 91 ms 17384 KB Output is correct
14 Correct 89 ms 17468 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2904 KB Output is correct
2 Correct 20 ms 5188 KB Output is correct
3 Correct 27 ms 8016 KB Output is correct
4 Correct 76 ms 19784 KB Output is correct
5 Correct 99 ms 21052 KB Output is correct
6 Correct 75 ms 22340 KB Output is correct
7 Correct 76 ms 24376 KB Output is correct
8 Correct 73 ms 19780 KB Output is correct
9 Correct 74 ms 22336 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 13 ms 2228 KB Output is correct
3 Correct 59 ms 12780 KB Output is correct
4 Correct 102 ms 16140 KB Output is correct
5 Correct 84 ms 16008 KB Output is correct
6 Correct 87 ms 15992 KB Output is correct
7 Correct 91 ms 16020 KB Output is correct
8 Correct 83 ms 16228 KB Output is correct
9 Correct 98 ms 16136 KB Output is correct
10 Correct 92 ms 16144 KB Output is correct
11 Correct 94 ms 16948 KB Output is correct
12 Correct 101 ms 18200 KB Output is correct
13 Correct 107 ms 17740 KB Output is correct
14 Correct 92 ms 17980 KB Output is correct
15 Correct 88 ms 16124 KB Output is correct
16 Correct 86 ms 16020 KB Output is correct
17 Correct 104 ms 17216 KB Output is correct
18 Correct 104 ms 17744 KB Output is correct
19 Correct 89 ms 15992 KB Output is correct
20 Correct 90 ms 18724 KB Output is correct
21 Correct 92 ms 17084 KB Output is correct
22 Correct 74 ms 17056 KB Output is correct
23 Correct 85 ms 16572 KB Output is correct
24 Correct 113 ms 16928 KB Output is correct
25 Correct 142 ms 23444 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 2648 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 2016 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -