oj.uz

Submission #1079669

# Submission time Handle Problem Language Result Execution time Memory
1079669 2024-08-28T20:58:09 Z skittles1412 Highway Tolls (IOI18_highway) C++17
90 / 100
 213 ms 18096 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 << ")";
}

inline vector<int> inverse(const vector<int>& arr) {
    int n = sz(arr);

    vector<int> ans(n);
    for (int i = 0; i < n; i++) {
        ans[arr[i]] = i;
    }

    return ans;
}

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

mt19937_64 cowng(1412);

struct G {
    int m;
    vector<int> perm, iperm;

    G() {}
    G(int m) : m(m) {
        perm = iota(m, 0);
        shuffle(begin(perm), end(perm), cowng);
        iperm = inverse(perm);
    }

    long query(const vector<int>& arr) const {
        vector<int> ans(m);
        for (int i = 0; i < m; i++) {
            ans[i] = arr[perm[i]];
        }
        return ask(ans);
    }

    void submit(int u, int v) const {
        answer(u, v);
    }
} G;

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 = G.query(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 G.query(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) {
        G.submit(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);
    G.submit(u1, u2);
}

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

        for (int i = 0; i < m; i++) {
            cv[G.perm[i]] = {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 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 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 1 ms 344 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 12 ms 1960 KB Output is correct
3 Correct 113 ms 16016 KB Output is correct
4 Correct 102 ms 15976 KB Output is correct
5 Correct 113 ms 16060 KB Output is correct
6 Correct 102 ms 15928 KB Output is correct
7 Correct 115 ms 16096 KB Output is correct
8 Correct 129 ms 15880 KB Output is correct
9 Correct 116 ms 15876 KB Output is correct
10 Correct 107 ms 16032 KB Output is correct
11 Correct 127 ms 15368 KB Output is correct
12 Correct 121 ms 15292 KB Output is correct
13 Correct 104 ms 15372 KB Output is correct
14 Correct 100 ms 15344 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2048 KB Output is correct
2 Correct 19 ms 3416 KB Output is correct
3 Correct 29 ms 4228 KB Output is correct
4 Correct 113 ms 13900 KB Output is correct
5 Correct 95 ms 13812 KB Output is correct
6 Correct 93 ms 14404 KB Output is correct
7 Correct 107 ms 11932 KB Output is correct
8 Correct 92 ms 14116 KB Output is correct
9 Correct 91 ms 12260 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 11 ms 2136 KB Output is correct
3 Correct 99 ms 11664 KB Output is correct
4 Correct 162 ms 14464 KB Output is correct
5 Correct 144 ms 15260 KB Output is correct
6 Correct 106 ms 13880 KB Output is correct
7 Correct 120 ms 14716 KB Output is correct
8 Correct 117 ms 14696 KB Output is correct
9 Correct 129 ms 15560 KB Output is correct
10 Correct 113 ms 16116 KB Output is correct
11 Correct 106 ms 14336 KB Output is correct
12 Correct 118 ms 15076 KB Output is correct
13 Correct 135 ms 14848 KB Output is correct
14 Correct 122 ms 14928 KB Output is correct
15 Correct 128 ms 15392 KB Output is correct
16 Correct 127 ms 14720 KB Output is correct
17 Correct 121 ms 14912 KB Output is correct
18 Correct 100 ms 14344 KB Output is correct
19 Correct 103 ms 14156 KB Output is correct
20 Correct 113 ms 13952 KB Output is correct
21 Correct 108 ms 15636 KB Output is correct
22 Correct 117 ms 14040 KB Output is correct
23 Correct 111 ms 16448 KB Output is correct
24 Correct 116 ms 16512 KB Output is correct
25 Correct 122 ms 15316 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2152 KB Output is correct
2 Correct 13 ms 2328 KB Output is correct
3 Correct 149 ms 16068 KB Output is correct
4 Correct 166 ms 16356 KB Output is correct
5 Correct 188 ms 17484 KB Output is correct
6 Correct 194 ms 17336 KB Output is correct
7 Correct 192 ms 17456 KB Output is correct
8 Correct 197 ms 17816 KB Output is correct
9 Correct 116 ms 10264 KB Output is correct
10 Correct 110 ms 10376 KB Output is correct
11 Correct 121 ms 11332 KB Output is correct
12 Correct 186 ms 15340 KB Output is correct
13 Correct 171 ms 17188 KB Output is correct
14 Correct 188 ms 17316 KB Output is correct
15 Correct 192 ms 17700 KB Output is correct
16 Correct 152 ms 12972 KB Output is correct
17 Correct 115 ms 16628 KB Output is correct
18 Correct 119 ms 16212 KB Output is correct
19 Correct 112 ms 16560 KB Output is correct
20 Correct 101 ms 15384 KB Output is correct
21 Correct 188 ms 18008 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2136 KB Output is correct
2 Correct 16 ms 2120 KB Output is correct
3 Correct 155 ms 15932 KB Output is correct
4 Correct 154 ms 16248 KB Output is correct
5 Correct 162 ms 16084 KB Output is correct
6 Correct 194 ms 17844 KB Output is correct
7 Correct 145 ms 15908 KB Output is correct
8 Correct 129 ms 16652 KB Output is correct
9 Correct 142 ms 16988 KB Output is correct
10 Correct 194 ms 18096 KB Output is correct
11 Correct 190 ms 17492 KB Output is correct
12 Partially correct 194 ms 18044 KB Output is partially correct
13 Correct 115 ms 11384 KB Output is correct
14 Correct 115 ms 11580 KB Output is correct
15 Correct 130 ms 11800 KB Output is correct
16 Correct 118 ms 10588 KB Output is correct
17 Correct 118 ms 11332 KB Output is correct
18 Correct 117 ms 10936 KB Output is correct
19 Correct 182 ms 15732 KB Output is correct
20 Correct 187 ms 16432 KB Output is correct
21 Correct 209 ms 17120 KB Output is correct
22 Correct 203 ms 17072 KB Output is correct
23 Correct 202 ms 17612 KB Output is correct
24 Correct 213 ms 17772 KB Output is correct
25 Correct 185 ms 16100 KB Output is correct
26 Correct 190 ms 17864 KB Output is correct
27 Correct 135 ms 15684 KB Output is correct
28 Correct 98 ms 15572 KB Output is correct
29 Correct 117 ms 15428 KB Output is correct
30 Correct 133 ms 14416 KB Output is correct
31 Correct 111 ms 16624 KB Output is correct
32 Partially correct 113 ms 14872 KB Output is partially correct
33 Correct 112 ms 16232 KB Output is correct
34 Correct 118 ms 16612 KB Output is correct
35 Correct 110 ms 16856 KB Output is correct
36 Correct 115 ms 15332 KB Output is correct
37 Correct 119 ms 15556 KB Output is correct
38 Correct 128 ms 14960 KB Output is correct
39 Partially correct 207 ms 17944 KB Output is partially correct
40 Correct 187 ms 18024 KB Output is correct
41 Correct 164 ms 18036 KB Output is correct
42 Correct 186 ms 18064 KB Output is correct