oj.uz

Submission #995479

# Submission time Handle Problem Language Result Execution time Memory
995479 2024-06-09T07:06:27 Z shiomusubi496 Highway Tolls (IOI18_highway) C++17
100 / 100
 146 ms 12220 KB 
#include "highway.h"
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)

using namespace std;

using ll = long long;

template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }

mt19937 mt(random_device{}());

struct edge {
    int to, idx;
    edge() = default;
    edge(int t, int i) : to(t), idx(i) {}
};

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    int M = U.size();
    vector<vector<edge>> G(N);
    rep (i, M) {
        G[U[i]].emplace_back(V[i], i);
        G[V[i]].emplace_back(U[i], i);
    }
    ll dist = ask(vector<int>(M, 0));

    int s;
    {
        int ok = 0, ng = M;
        while (ng - ok > 1) {
            int mid = (ok + ng) / 2;
            vector<int> f(M);
            rep (i, M) f[i] = i < mid;
            if (ask(f) != dist) ng = mid;
            else ok = mid;
        }
        // ok 本目までの辺で最短経路のカットになる
        // 以下 ok 未満の辺は全て B として、 ok の各端点につながる頂点を探す
        s = ok;
    }
    int sv0 = U[s], sv1 = V[s];
    // sv0 から行く方が sv1 からより近い頂点集合の中に v0 がいる
    vector<int> dist1(N, -1), dist2(N, -1);
    queue<int> que;
    dist1[sv0] = 0;
    que.push(sv0);
    while (!que.empty()) {
        int v = que.front(); que.pop();
        for (auto e : G[v]) {
            if (dist1[e.to] == -1 && e.idx > s) {
                dist1[e.to] = dist1[v] + 1;
                que.push(e.to);
            }
        }
    }
    dist2[sv1] = 0;
    que.push(sv1);
    while (!que.empty()) {
        int v = que.front(); que.pop();
        for (auto e : G[v]) {
            if (dist2[e.to] == -1 && e.idx > s) {
                dist2[e.to] = dist2[v] + 1;
                que.push(e.to);
            }
        }
    }
    vector<int> near0(N);
    rep (i, N) {
        if (dist1[i] != -1 && (dist2[i] == -1 || dist1[i] < dist2[i])) near0[i] = 1;
        if (dist2[i] != -1 && (dist1[i] == -1 || dist2[i] < dist1[i])) near0[i] = -1;
    }
    // 遠い辺から無効にしていったとき、はじめて距離が変わったときの辺の端点が答え？
    int ans0, ans1;
    {
        vector<pair<int, int>> es;
        rep2 (i, s + 1, M) {
            if (near0[U[i]] != 1 || near0[V[i]] != 1) continue;
            int d = max(dist1[U[i]], dist1[V[i]]);
            es.emplace_back(d, i);
        }
        sort(rall(es));
        int ok = es.size() + 1, ng = 0;
        while (ok - ng > 1) {
            int mid = (ok + ng) / 2;
            vector<int> f(M);
            rep (i, s) f[i] = 1;
            rep (i, mid) f[es[i].second] = 1;
            if (ask(f) != dist) ok = mid;
            else ng = mid;
        }
        if (ok == es.size() + 1) ans0 = sv0;
        else {
            --ok;
            if (dist1[U[es[ok].second]] > dist1[V[es[ok].second]]) ans0 = U[es[ok].second];
            else ans0 = V[es[ok].second];
        }
    }
    {
        vector<pair<int, int>> es;
        rep2 (i, s + 1, M) {
            if (near0[U[i]] != -1 || near0[V[i]] != -1) continue;
            int d = max(dist2[U[i]], dist2[V[i]]);
            es.emplace_back(d, i);
        }
        sort(rall(es));
        int ok = es.size() + 1, ng = 0;
        while (ok - ng > 1) {
            int mid = (ok + ng) / 2;
            vector<int> f(M);
            rep (i, s) f[i] = 1;
            rep (i, mid) f[es[i].second] = 1;
            if (ask(f) != dist) ok = mid;
            else ng = mid;
        }
        if (ok == es.size() + 1) ans1 = sv1;
        else {
            --ok;
            if (dist2[U[es[ok].second]] > dist2[V[es[ok].second]]) ans1 = U[es[ok].second];
            else ans1 = V[es[ok].second];
        }
    }
    answer(ans0, ans1);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:99:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         if (ok == es.size() + 1) ans0 = sv0;
      |             ~~~^~~~~~~~~~~~~~~~
highway.cpp:123:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         if (ok == es.size() + 1) ans1 = sv1;
      |             ~~~^~~~~~~~~~~~~~~~

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 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 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 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 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 344 KB Output is correct
2 Correct 8 ms 1368 KB Output is correct
3 Correct 87 ms 9696 KB Output is correct
4 Correct 89 ms 9816 KB Output is correct
5 Correct 86 ms 9960 KB Output is correct
6 Correct 77 ms 9288 KB Output is correct
7 Correct 100 ms 9220 KB Output is correct
8 Correct 85 ms 9720 KB Output is correct
9 Correct 81 ms 9184 KB Output is correct
10 Correct 77 ms 9424 KB Output is correct
11 Correct 74 ms 8452 KB Output is correct
12 Correct 101 ms 8836 KB Output is correct
13 Correct 79 ms 9340 KB Output is correct
14 Correct 87 ms 9188 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1468 KB Output is correct
2 Correct 16 ms 2296 KB Output is correct
3 Correct 21 ms 2880 KB Output is correct
4 Correct 64 ms 8780 KB Output is correct
5 Correct 68 ms 8788 KB Output is correct
6 Correct 66 ms 9176 KB Output is correct
7 Correct 66 ms 8300 KB Output is correct
8 Correct 64 ms 8848 KB Output is correct
9 Correct 64 ms 8624 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 9 ms 1368 KB Output is correct
3 Correct 65 ms 7820 KB Output is correct
4 Correct 82 ms 9700 KB Output is correct
5 Correct 66 ms 8688 KB Output is correct
6 Correct 82 ms 8660 KB Output is correct
7 Correct 80 ms 9224 KB Output is correct
8 Correct 70 ms 8852 KB Output is correct
9 Correct 94 ms 9716 KB Output is correct
10 Correct 87 ms 9332 KB Output is correct
11 Correct 96 ms 9320 KB Output is correct
12 Correct 87 ms 8848 KB Output is correct
13 Correct 94 ms 8772 KB Output is correct
14 Correct 76 ms 8360 KB Output is correct
15 Correct 71 ms 8804 KB Output is correct
16 Correct 69 ms 8576 KB Output is correct
17 Correct 88 ms 9328 KB Output is correct
18 Correct 101 ms 9204 KB Output is correct
19 Correct 73 ms 8632 KB Output is correct
20 Correct 64 ms 8396 KB Output is correct
21 Correct 75 ms 9704 KB Output is correct
22 Correct 65 ms 9376 KB Output is correct
23 Correct 81 ms 9472 KB Output is correct
24 Correct 77 ms 9376 KB Output is correct
25 Correct 85 ms 9488 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1368 KB Output is correct
2 Correct 11 ms 1588 KB Output is correct
3 Correct 104 ms 10112 KB Output is correct
4 Correct 114 ms 10664 KB Output is correct
5 Correct 125 ms 11616 KB Output is correct
6 Correct 138 ms 12220 KB Output is correct
7 Correct 126 ms 10980 KB Output is correct
8 Correct 113 ms 11612 KB Output is correct
9 Correct 88 ms 6980 KB Output is correct
10 Correct 100 ms 7692 KB Output is correct
11 Correct 104 ms 8400 KB Output is correct
12 Correct 124 ms 10216 KB Output is correct
13 Correct 146 ms 10580 KB Output is correct
14 Correct 137 ms 11156 KB Output is correct
15 Correct 143 ms 11456 KB Output is correct
16 Correct 114 ms 8908 KB Output is correct
17 Correct 71 ms 9636 KB Output is correct
18 Correct 71 ms 9276 KB Output is correct
19 Correct 81 ms 10060 KB Output is correct
20 Correct 79 ms 9736 KB Output is correct
21 Correct 133 ms 11396 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1368 KB Output is correct
2 Correct 10 ms 1624 KB Output is correct
3 Correct 103 ms 9680 KB Output is correct
4 Correct 105 ms 9852 KB Output is correct
5 Correct 110 ms 10144 KB Output is correct
6 Correct 130 ms 11520 KB Output is correct
7 Correct 90 ms 10160 KB Output is correct
8 Correct 122 ms 10348 KB Output is correct
9 Correct 104 ms 10784 KB Output is correct
10 Correct 131 ms 10996 KB Output is correct
11 Correct 129 ms 11336 KB Output is correct
12 Correct 125 ms 11036 KB Output is correct
13 Correct 93 ms 7920 KB Output is correct
14 Correct 93 ms 7296 KB Output is correct
15 Correct 136 ms 8512 KB Output is correct
16 Correct 112 ms 7700 KB Output is correct
17 Correct 116 ms 8464 KB Output is correct
18 Correct 103 ms 7788 KB Output is correct
19 Correct 128 ms 10136 KB Output is correct
20 Correct 133 ms 11140 KB Output is correct
21 Correct 138 ms 11044 KB Output is correct
22 Correct 139 ms 10988 KB Output is correct
23 Correct 135 ms 11368 KB Output is correct
24 Correct 130 ms 11432 KB Output is correct
25 Correct 133 ms 11368 KB Output is correct
26 Correct 132 ms 11576 KB Output is correct
27 Correct 89 ms 9600 KB Output is correct
28 Correct 84 ms 10388 KB Output is correct
29 Correct 85 ms 10288 KB Output is correct
30 Correct 79 ms 10244 KB Output is correct
31 Correct 80 ms 10464 KB Output is correct
32 Correct 80 ms 10232 KB Output is correct
33 Correct 81 ms 10588 KB Output is correct
34 Correct 97 ms 9848 KB Output is correct
35 Correct 76 ms 10016 KB Output is correct
36 Correct 78 ms 10116 KB Output is correct
37 Correct 89 ms 9960 KB Output is correct
38 Correct 79 ms 10188 KB Output is correct
39 Correct 140 ms 11964 KB Output is correct
40 Correct 137 ms 11520 KB Output is correct
41 Correct 143 ms 11580 KB Output is correct
42 Correct 138 ms 11528 KB Output is correct