oj.uz

답안 #1085708

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1085708 2024-09-08T15:25:03 Z vladilius 통행료 (IOI18_highway) C++17
90 / 100
 178 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);
 
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 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 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 9 ms 2040 KB Output is correct
3 Correct 105 ms 15820 KB Output is correct
4 Correct 104 ms 16044 KB Output is correct
5 Correct 103 ms 15988 KB Output is correct
6 Correct 115 ms 15804 KB Output is correct
7 Correct 111 ms 15800 KB Output is correct
8 Correct 97 ms 15696 KB Output is correct
9 Correct 103 ms 16100 KB Output is correct
10 Correct 99 ms 15812 KB Output is correct
11 Correct 113 ms 16944 KB Output is correct
12 Correct 124 ms 18340 KB Output is correct
13 Correct 97 ms 17168 KB Output is correct
14 Correct 97 ms 17500 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 2904 KB Output is correct
2 Correct 18 ms 4900 KB Output is correct
3 Correct 27 ms 8100 KB Output is correct
4 Correct 79 ms 20328 KB Output is correct
5 Correct 106 ms 20796 KB Output is correct
6 Correct 86 ms 23156 KB Output is correct
7 Correct 86 ms 24104 KB Output is correct
8 Correct 93 ms 21788 KB Output is correct
9 Correct 77 ms 22424 KB Output is correct

Subtask #4
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 11 ms 2136 KB Output is correct
3 Correct 67 ms 12396 KB Output is correct
4 Correct 103 ms 15828 KB Output is correct
5 Correct 94 ms 15800 KB Output is correct
6 Correct 97 ms 15808 KB Output is correct
7 Correct 83 ms 15812 KB Output is correct
8 Correct 102 ms 15784 KB Output is correct
9 Correct 113 ms 15748 KB Output is correct
10 Correct 104 ms 15808 KB Output is correct
11 Correct 106 ms 16568 KB Output is correct
12 Correct 106 ms 17992 KB Output is correct
13 Correct 115 ms 17408 KB Output is correct
14 Correct 105 ms 17492 KB Output is correct
15 Correct 90 ms 15808 KB Output is correct
16 Correct 90 ms 16036 KB Output is correct
17 Correct 105 ms 17200 KB Output is correct
18 Correct 106 ms 17288 KB Output is correct
19 Correct 94 ms 15812 KB Output is correct
20 Correct 105 ms 18656 KB Output is correct
21 Correct 97 ms 16476 KB Output is correct
22 Correct 79 ms 16472 KB Output is correct
23 Correct 92 ms 16420 KB Output is correct
24 Correct 91 ms 16612 KB Output is correct
25 Correct 105 ms 23488 KB Output is correct

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 2044 KB Output is correct
2 Correct 13 ms 2128 KB Output is correct
3 Correct 118 ms 16336 KB Output is correct
4 Correct 108 ms 16484 KB Output is correct
5 Correct 161 ms 17508 KB Output is correct
6 Correct 145 ms 17312 KB Output is correct
7 Correct 161 ms 17264 KB Output is correct
8 Correct 155 ms 17248 KB Output is correct
9 Correct 101 ms 9424 KB Output is correct
10 Correct 101 ms 9264 KB Output is correct
11 Correct 105 ms 11344 KB Output is correct
12 Correct 136 ms 14896 KB Output is correct
13 Correct 142 ms 15972 KB Output is correct
14 Correct 168 ms 17432 KB Output is correct
15 Correct 154 ms 17012 KB Output is correct
16 Correct 121 ms 11092 KB Output is correct
17 Correct 117 ms 16508 KB Output is correct
18 Correct 96 ms 17288 KB Output is correct
19 Correct 93 ms 16428 KB Output is correct
20 Correct 94 ms 16428 KB Output is correct
21 Correct 136 ms 18000 KB Output is correct

Subtask #6
21.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 2048 KB Output is correct
2 Correct 13 ms 2136 KB Output is correct
3 Correct 95 ms 16156 KB Output is correct
4 Correct 121 ms 16576 KB Output is correct
5 Correct 120 ms 16664 KB Output is correct
6 Correct 152 ms 17424 KB Output is correct
7 Correct 119 ms 16124 KB Output is correct
8 Correct 121 ms 16252 KB Output is correct
9 Correct 117 ms 16476 KB Output is correct
10 Correct 165 ms 17196 KB Output is correct
11 Partially correct 154 ms 17232 KB Output is partially correct
12 Partially correct 147 ms 17424 KB Output is partially correct
13 Correct 128 ms 11316 KB Output is correct
14 Correct 125 ms 9480 KB Output is correct
15 Correct 107 ms 11444 KB Output is correct
16 Correct 97 ms 9512 KB Output is correct
17 Correct 101 ms 11312 KB Output is correct
18 Correct 102 ms 9280 KB Output is correct
19 Correct 145 ms 14968 KB Output is correct
20 Correct 148 ms 15824 KB Output is correct
21 Partially correct 164 ms 17240 KB Output is partially correct
22 Partially correct 151 ms 17000 KB Output is partially correct
23 Correct 174 ms 17012 KB Output is correct
24 Correct 156 ms 17280 KB Output is correct
25 Correct 178 ms 17300 KB Output is correct
26 Correct 145 ms 17092 KB Output is correct
27 Correct 94 ms 16316 KB Output is correct
28 Correct 93 ms 16200 KB Output is correct
29 Correct 91 ms 16572 KB Output is correct
30 Correct 106 ms 16344 KB Output is correct
31 Correct 101 ms 16416 KB Output is correct
32 Correct 99 ms 16280 KB Output is correct
33 Correct 101 ms 16508 KB Output is correct
34 Correct 96 ms 16292 KB Output is correct
35 Correct 90 ms 16392 KB Output is correct
36 Correct 113 ms 16572 KB Output is correct
37 Correct 112 ms 16560 KB Output is correct
38 Correct 99 ms 16424 KB Output is correct
39 Correct 147 ms 18520 KB Output is correct
40 Correct 148 ms 18828 KB Output is correct
41 Correct 156 ms 17792 KB Output is correct
42 Partially correct 146 ms 17516 KB Output is partially correct