oj.uz

Submission #1079659

# Submission time Handle Problem Language Result Execution time Memory
1079659 2024-08-28T20:31:06 Z skittles1412 Highway Tolls (IOI18_highway) C++17
90 / 100
 202 ms 17104 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;
}

template <typename A, typename B>
ostream& operator<<(ostream& out, const pair<A, B>& p) {
    return out << "(" << p.first << ", " << p.second << ")";
}

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

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

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

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

        dist[u] = d;
        q.push(u);
        if (src != -1) {
            tedges.emplace_back(src, u);
        }
    };

    push(src, -1, 0);

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

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

    return {dist, tedges};
}

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, tedges] = bfs([&]() {
        vector<vector<int>> graph(n);

        for (auto& [u, v] : edges) {
            if (u >= root && v >= root) {
                graph[u].push_back(v);
                graph[v].push_back(u);
            }
        }

        return graph;
    }(), root);
    dbg(tedges);
    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;
    }

    dbg(u1);
    vector<int> rem_nodes;
    {
        vector<vector<int>> graph(n);
        for (auto& [u, v] : tedges) {
            graph[u].push_back(v);
            graph[v].push_back(u);
        }

        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 : 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 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 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 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 600 KB Output is correct
2 Correct 12 ms 1880 KB Output is correct
3 Correct 106 ms 15056 KB Output is correct
4 Correct 109 ms 15396 KB Output is correct
5 Correct 96 ms 15156 KB Output is correct
6 Correct 100 ms 15116 KB Output is correct
7 Correct 108 ms 15132 KB Output is correct
8 Correct 109 ms 15156 KB Output is correct
9 Correct 101 ms 15168 KB Output is correct
10 Correct 103 ms 15156 KB Output is correct
11 Correct 104 ms 14328 KB Output is correct
12 Correct 112 ms 14328 KB Output is correct
13 Correct 102 ms 14408 KB Output is correct
14 Correct 91 ms 14320 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1880 KB Output is correct
2 Correct 16 ms 3268 KB Output is correct
3 Correct 23 ms 4020 KB Output is correct
4 Correct 71 ms 13176 KB Output is correct
5 Correct 70 ms 13136 KB Output is correct
6 Correct 75 ms 13732 KB Output is correct
7 Correct 90 ms 10880 KB Output is correct
8 Correct 74 ms 13472 KB Output is correct
9 Correct 75 ms 11516 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 12 ms 2044 KB Output is correct
3 Correct 93 ms 11524 KB Output is correct
4 Correct 125 ms 14032 KB Output is correct
5 Correct 134 ms 14716 KB Output is correct
6 Correct 108 ms 13168 KB Output is correct
7 Correct 99 ms 14028 KB Output is correct
8 Correct 131 ms 13736 KB Output is correct
9 Correct 134 ms 14772 KB Output is correct
10 Correct 101 ms 15104 KB Output is correct
11 Correct 98 ms 13624 KB Output is correct
12 Correct 103 ms 14228 KB Output is correct
13 Correct 113 ms 14188 KB Output is correct
14 Correct 117 ms 14280 KB Output is correct
15 Correct 136 ms 14812 KB Output is correct
16 Correct 115 ms 13696 KB Output is correct
17 Correct 125 ms 14264 KB Output is correct
18 Correct 96 ms 13580 KB Output is correct
19 Correct 92 ms 13060 KB Output is correct
20 Correct 95 ms 13248 KB Output is correct
21 Correct 112 ms 14932 KB Output is correct
22 Correct 94 ms 13432 KB Output is correct
23 Correct 102 ms 16060 KB Output is correct
24 Correct 111 ms 16020 KB Output is correct
25 Correct 125 ms 14756 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1900 KB Output is correct
2 Correct 13 ms 2136 KB Output is correct
3 Correct 130 ms 15220 KB Output is correct
4 Correct 151 ms 15340 KB Output is correct
5 Correct 198 ms 16568 KB Output is correct
6 Correct 176 ms 16264 KB Output is correct
7 Correct 174 ms 16496 KB Output is correct
8 Correct 202 ms 16944 KB Output is correct
9 Correct 104 ms 8764 KB Output is correct
10 Correct 101 ms 9132 KB Output is correct
11 Correct 112 ms 10060 KB Output is correct
12 Correct 161 ms 14384 KB Output is correct
13 Correct 140 ms 15808 KB Output is correct
14 Correct 173 ms 16236 KB Output is correct
15 Correct 198 ms 16616 KB Output is correct
16 Correct 145 ms 12352 KB Output is correct
17 Correct 102 ms 15984 KB Output is correct
18 Correct 101 ms 15976 KB Output is correct
19 Correct 111 ms 16404 KB Output is correct
20 Correct 100 ms 15340 KB Output is correct
21 Correct 164 ms 16868 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1948 KB Output is correct
2 Correct 12 ms 1880 KB Output is correct
3 Correct 145 ms 14888 KB Output is correct
4 Partially correct 156 ms 15592 KB Output is partially correct
5 Correct 146 ms 15016 KB Output is correct
6 Correct 173 ms 16788 KB Output is correct
7 Correct 140 ms 15052 KB Output is correct
8 Correct 123 ms 15624 KB Output is correct
9 Correct 122 ms 15876 KB Output is correct
10 Correct 187 ms 17104 KB Output is correct
11 Correct 178 ms 16328 KB Output is correct
12 Partially correct 171 ms 16984 KB Output is partially correct
13 Correct 107 ms 10136 KB Output is correct
14 Correct 106 ms 10676 KB Output is correct
15 Correct 138 ms 10892 KB Output is correct
16 Correct 115 ms 9828 KB Output is correct
17 Correct 109 ms 10116 KB Output is correct
18 Correct 106 ms 10028 KB Output is correct
19 Correct 166 ms 14764 KB Output is correct
20 Correct 170 ms 15408 KB Output is correct
21 Correct 170 ms 16264 KB Output is correct
22 Correct 191 ms 15932 KB Output is correct
23 Correct 178 ms 16888 KB Output is correct
24 Correct 184 ms 16760 KB Output is correct
25 Correct 164 ms 15324 KB Output is correct
26 Correct 172 ms 16696 KB Output is correct
27 Correct 110 ms 15600 KB Output is correct
28 Correct 91 ms 15216 KB Output is correct
29 Correct 104 ms 15192 KB Output is correct
30 Correct 116 ms 13992 KB Output is correct
31 Correct 101 ms 16128 KB Output is correct
32 Partially correct 98 ms 14580 KB Output is partially correct
33 Correct 101 ms 15960 KB Output is correct
34 Correct 105 ms 16312 KB Output is correct
35 Correct 103 ms 16212 KB Output is correct
36 Correct 121 ms 15020 KB Output is correct
37 Correct 108 ms 15440 KB Output is correct
38 Correct 123 ms 14328 KB Output is correct
39 Correct 190 ms 17084 KB Output is correct
40 Correct 168 ms 16808 KB Output is correct
41 Correct 161 ms 16756 KB Output is correct
42 Correct 184 ms 16828 KB Output is correct