oj.uz

Submission #1079655

# Submission time Handle Problem Language Result Execution time Memory
1079655 2024-08-28T20:10:16 Z skittles1412 Highway Tolls (IOI18_highway) C++17
51 / 100
 151 ms 11404 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using ll = long long;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

inline void init_io() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
}

template <typename T>
vector<T> iota(int n, T x) {
    vector<T> ans(n);
    iota(begin(ans), end(ans), x);
    return ans;
}

template <typename T>
vector<T>& operator+=(vector<T>& a, const vector<T>& b) {
    a.insert(end(a), begin(b), end(b));
    return a;
}

template <typename T>
vector<T> operator+(vector<T> a, const vector<T>& b) {
    return a += b;
}

template <typename Cb>
struct CmpByKey {
    Cb cb;

    CmpByKey(Cb cb) : cb(cb) {}

    template <typename T>
    bool operator()(const T& a, const T& b) const {
        return cb(a) < cb(b);
    }
};

template <typename T, typename Cb>
T first_true(T l, T r, const Cb& cb) {
    while (l < r) {
        T mid = (l + r) / 2;

        if (cb(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    return l;
}

template <typename T, typename Cb>
T last_true(T l, T r, const Cb& cb) {
    while (l < r) {
        T mid = (l + r + 1) / 2;

        if (cb(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }

    return l;
}

template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
    out << "[";
    for (int i = 0; i < sz(arr); i++) {
        if (i) {
            out << ", ";
        }
        out << arr[i];
    }
    return out << "]";
}

template <typename T>
T negated(T arr) {
    for (auto& a : arr) {
        a = -a;
    }
    return arr;
}

ll ask(const std::vector<int>& w);
void answer(int s, int t);

vector<int> bfs(const vector<vector<pair<int, int>>>& graph, int src) {
    int n = sz(graph);

    vector dist(n, -1);
    queue<int> q;

    auto push = [&](int u, int d) -> void {
        if (dist[u] != -1) {
            return;
        }

        dist[u] = d;
        q.push(u);
    };

    push(src, 0);

    while (sz(q)) {
        int u = q.front();
        q.pop();

        for (auto& [v, _ei] : graph[u]) {
            push(v, dist[u] + 1);
        }
    }

    return dist;
}

void solve(int n, const vector<pair<int, int>>& edges, int wa, int) {
    int m = sz(edges);
    dbg(m);

    vector<vector<pair<int, int>>> graph(n);

    for (int i = 0; i < m; i++) {
        auto& [u, v] = edges[i];
        graph[u].emplace_back(v, i);
        graph[v].emplace_back(u, i);
    }

    long base = ask(vector<int>(m, 0));

    auto nodes_blocked = [&](const vector<int>& nodes) -> vector<int> {
        vector<int> cv(m);

        for (auto& u : nodes) {
            for (auto& [_v, ei] : graph[u]) {
                cv[ei] = true;
            }
        }

        return cv;
    };
    auto ask_nodes = [&](const vector<int>& nodes) -> bool {
        return ask(nodes_blocked(nodes)) > base;
    };

    int root = first_true(0, n, [&](int x) -> bool {
        return ask_nodes(iota(x + 1, 0));
    });
    dbg(root);

    auto base_block = iota(root, 0);
    dbg(base_block);

    auto dist = bfs(graph, root);
    auto ord = iota(n, 0);
    sort(begin(ord), end(ord), CmpByKey([&](int u) -> int {
        return dist[u];
    }));

    int u1_ind = last_true(0, n,
                           [&](int x) -> bool {
        return ask_nodes(base_block + vector(begin(ord) + x, end(ord)));
    }),
        u1 = ord[u1_ind];

    if (dist[u1] == base / wa) {
        answer(u1, root);
        return;
    }

    vector<int> rem_nodes;
    {
        vector<bool> vis(n);
        vector<int> q;

        for (int i = 0; i <= root; i++) {
            vis[i] = true;
        }

        auto push = [&](int u) -> void {
            if (vis[u]) {
                return;
            }
            vis[u] = true;
            q.push_back(u);
        };

        push(u1);
        while (sz(q)) {
            int u = q.back();
            q.pop_back();

            for (auto& [v, _ei] : graph[u]) {
                push(v);
            }
        }

        for (auto& a : ord) {
            if (!vis[a]) {
                rem_nodes.push_back(a);
            }
        }
    }

    int u2_ind = last_true(0, sz(rem_nodes),
                           [&](int x) -> bool {
        return ask_nodes(base_block +
                         vector(begin(rem_nodes) + x, end(rem_nodes)));
    }),
        u2 = rem_nodes[u2_ind];

    dbg(u1, u2);
    dbg(ord, u1_ind, u2_ind);
    answer(u1, u2);
}

void find_pair(int n,
               vector<int> edges_u,
               vector<int> edges_v,
               int wa,
               int wb) {
    return solve(n, [&]() {
        vector<pair<int, int>> cv;

        for (int i = 0; i < sz(edges_u); i++) {
            cv.emplace_back(edges_u[i], edges_v[i]);
        }

        return cv;
    }(), wa, wb);
}

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 1 ms 344 KB Output is correct
7 Correct 1 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 0 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 10 ms 1548 KB Output is correct
3 Correct 106 ms 9832 KB Output is correct
4 Correct 87 ms 9864 KB Output is correct
5 Correct 87 ms 10028 KB Output is correct
6 Correct 75 ms 9820 KB Output is correct
7 Correct 103 ms 10400 KB Output is correct
8 Correct 105 ms 10120 KB Output is correct
9 Correct 94 ms 10448 KB Output is correct
10 Correct 91 ms 9896 KB Output is correct
11 Correct 99 ms 9656 KB Output is correct
12 Correct 91 ms 9408 KB Output is correct
13 Correct 94 ms 9768 KB Output is correct
14 Correct 87 ms 9248 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1508 KB Output is correct
2 Correct 19 ms 2484 KB Output is correct
3 Correct 26 ms 3924 KB Output is correct
4 Correct 72 ms 9888 KB Output is correct
5 Correct 95 ms 10252 KB Output is correct
6 Correct 92 ms 9392 KB Output is correct
7 Correct 94 ms 11140 KB Output is correct
8 Correct 64 ms 9368 KB Output is correct
9 Correct 82 ms 10696 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 11 ms 1420 KB Output is correct
3 Correct 96 ms 8256 KB Output is correct
4 Correct 127 ms 11168 KB Output is correct
5 Correct 135 ms 11404 KB Output is correct
6 Correct 151 ms 11024 KB Output is correct
7 Correct 108 ms 10584 KB Output is correct
8 Correct 117 ms 10564 KB Output is correct
9 Correct 102 ms 9976 KB Output is correct
10 Correct 96 ms 9984 KB Output is correct
11 Correct 124 ms 10312 KB Output is correct
12 Correct 101 ms 9400 KB Output is correct
13 Correct 118 ms 9496 KB Output is correct
14 Correct 119 ms 9840 KB Output is correct
15 Correct 109 ms 10560 KB Output is correct
16 Correct 131 ms 10616 KB Output is correct
17 Correct 113 ms 9524 KB Output is correct
18 Correct 121 ms 10276 KB Output is correct
19 Correct 120 ms 10596 KB Output is correct
20 Correct 123 ms 10744 KB Output is correct
21 Correct 97 ms 10164 KB Output is correct
22 Correct 104 ms 10924 KB Output is correct
23 Correct 114 ms 10120 KB Output is correct
24 Correct 96 ms 10164 KB Output is correct
25 Correct 90 ms 9332 KB Output is correct

Subtask #5
0 / 18.0

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