oj.uz

Submission #1081717

# Submission time Handle Problem Language Result Execution time Memory
1081717 2024-08-30T09:32:59 Z vladilius Highway Tolls (IOI18_highway) C++17
51 / 100
 120 ms 24160 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
#define ins insert

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;
    queue<int> q;
    q.push(V[x]);
    used[V[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);
        }
    }
    
    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:34:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |             while (all.size() > k) all.pop_back();
      |                    ~~~~~~~~~~~^~~
highway.cpp:37:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |             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 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 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 688 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 1 ms 600 KB Output is correct
2 Correct 9 ms 2116 KB Output is correct
3 Correct 96 ms 15984 KB Output is correct
4 Correct 101 ms 16276 KB Output is correct
5 Correct 94 ms 16008 KB Output is correct
6 Correct 85 ms 15992 KB Output is correct
7 Correct 109 ms 16040 KB Output is correct
8 Correct 92 ms 15948 KB Output is correct
9 Correct 86 ms 15984 KB Output is correct
10 Correct 100 ms 16236 KB Output is correct
11 Correct 90 ms 16792 KB Output is correct
12 Correct 107 ms 18240 KB Output is correct
13 Correct 84 ms 17384 KB Output is correct
14 Correct 88 ms 17588 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2904 KB Output is correct
2 Correct 16 ms 5192 KB Output is correct
3 Correct 26 ms 8024 KB Output is correct
4 Correct 71 ms 19772 KB Output is correct
5 Correct 78 ms 21060 KB Output is correct
6 Correct 68 ms 22316 KB Output is correct
7 Correct 77 ms 24160 KB Output is correct
8 Correct 71 ms 19776 KB Output is correct
9 Correct 68 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 9 ms 2136 KB Output is correct
3 Correct 74 ms 12756 KB Output is correct
4 Correct 97 ms 16148 KB Output is correct
5 Correct 84 ms 16308 KB Output is correct
6 Correct 92 ms 16248 KB Output is correct
7 Correct 87 ms 16012 KB Output is correct
8 Correct 87 ms 16124 KB Output is correct
9 Correct 118 ms 15984 KB Output is correct
10 Correct 88 ms 16148 KB Output is correct
11 Correct 87 ms 17028 KB Output is correct
12 Correct 95 ms 18212 KB Output is correct
13 Correct 86 ms 17724 KB Output is correct
14 Correct 83 ms 17980 KB Output is correct
15 Correct 86 ms 16148 KB Output is correct
16 Correct 93 ms 15984 KB Output is correct
17 Correct 83 ms 17204 KB Output is correct
18 Correct 94 ms 17880 KB Output is correct
19 Correct 80 ms 15996 KB Output is correct
20 Correct 87 ms 18616 KB Output is correct
21 Correct 83 ms 17084 KB Output is correct
22 Correct 79 ms 17076 KB Output is correct
23 Correct 88 ms 16476 KB Output is correct
24 Correct 94 ms 16944 KB Output is correct
25 Correct 120 ms 23432 KB Output is correct

Subtask #5
0 / 18.0

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