Submission #1258588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258588		biank	ICC (CEOI16_icc)	C++20	100 / 100	71 ms	640 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
 
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
 
#define pb push_back
#define eb emplace_back
 
#define fst first
#define snd second
 
using namespace std;
 
using vi = vector<int>;
using ii = pair<int, int>;
 
struct DSU {
    vi p;
    vector<vi> c;
    DSU(int n) : p(n), c(n) {
        forn(i, n) p[i] = i, c[i] = vi{i};
    }
    int find(int x) {
        if (p[x] == x) return x;
        return p[x] = find(p[x]);
    }
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (sz(c[x]) > sz(c[y])) swap(x, y);
        for (int u : c[y]) c[x].pb(u);
        c[y].clear(), p[y] = x;
        return true;
    }
};
 
bool ask(vector<ii> a, vector<ii> b) {
    int A[sz(a)], B[sz(b)];
    forn(i, sz(a)) A[i] = a[i].fst + 1;
    forn(i, sz(b)) B[i] = b[i].fst + 1;
    return query(sz(a), sz(b), A, B);
}
 
ii solve(vector<ii> &a, vector<ii> &b, int k) {
    int lo = 0, hi = sz(b);
    while (hi - lo > 1) {
        int mid = (lo + hi) / 2;
        if (ask(a, vector<ii>(begin(b), begin(b) + mid))) hi = mid;
        else lo = mid;
    }
    b = {b[lo]};
    vector<ii> new_a;
    forn(i, sz(a)) {
        int flag = true;
        forn(bit, k) if ((b.back().snd >> bit & 1) !=
                         (a[i].snd >> bit & 1)) {
            flag = false;
        }
        if (flag) new_a.pb(a[i]);
    }
    a = new_a;
    lo = 0, hi = sz(a);
    while (hi - lo > 1) {
        int mid = (lo + hi) / 2;
        if (ask(vector<ii>(begin(a), begin(a) + mid), b)) hi = mid;
        else lo = mid;
    }
    a = {a[lo]};
    return ii{a.back().fst, b.back().fst};
}
 
void run(int N) {
    DSU dsu(N);
    forn(_, N - 1) {
        vector<vi> components;
        forn(u, N) if (dsu.p[u] == u) components.pb(dsu.c[u]);
        int bit = 0;
        while ((1 << bit) < sz(components)) {
            vector<ii> v[2];
            forn(i, sz(components)) {
                for (int u : components[i]) v[i >> bit & 1].eb(u, i);
            }
            if (ask(v[0], v[1])) {
                auto [a, b] = solve(v[0], v[1], bit);
                setRoad(a + 1, b + 1);
                dsu.unite(a, b);
                break;
            }
            bit++;
        }
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10