Submission #1247713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247713		dbence	Pictionary (COCI18_pictionary)	C++20	140 / 140	110 ms	44932 KiB

pictionary

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define len(x) (x).size()
#define lsb(x) (x) & (-x)
#define l(x) (x << 1) + 1
#define r(x) (x << 1) + 2
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

template <typename T>
void print(T t) {
    cout << t << "\n";
}

template <typename T, typename... Args>
void print(T t, Args ...args) {
    cout << t << " ";
    print(args...);
}

const int N = 1e5 + 1;
int n, m, q, ci, ans[N];

struct Query {
    int a, b, i;
};
vector <Query> qry;

struct Dsu {
    int cnt[N];
    int par[N];
    vector <pair <pii, pii>> updates;

    void unite(int u, int v) {
        u = root(u);
        v = root(v);
        if (u == v) {
            updates.pb({{u, v}, {cnt[u], par[v]}});
            return;
        }
        if (cnt[u] < cnt[v]) {
            swap(u, v);
        }
        updates.pb({{u, v}, {cnt[u], par[v]}});
        cnt[u] += cnt[v];
        par[v] = u;
    }
    int root(int u) {
        return par[u] == u? u: root(par[u]);
    }
    void rollback() {
        auto p = updates.back();
        updates.pop_back();

        cnt[p.xx.xx] = p.yy.xx;
        par[p.xx.yy] = p.yy.yy;
    }
} dsu;

void add() {
    int i = ++ci;
    int x = m - i + 1;
    for (int i = x; i <= n; i += x) {
        dsu.unite(x, i);
    }
}

void rem() {
    int i = ci--;
    int x = m - i + 1;
    for (int i = x; i <= n; i += x) {
        dsu.rollback();
    }
}

void bin_search(int l, int r, vector <Query> &qry) {
    if (l == r) {
        for (auto p: qry) {
            ans[p.i] = l;
        }
        return;
    }
    vector <Query> lef, rig;

    int mid = l + r >> 1;
    while (ci < mid) add();
    while (ci > mid) rem();
    for (auto &p: qry) {
        if (dsu.root(p.a) == dsu.root(p.b)) {
            lef.pb(p);
        } else {
            rig.pb(p);
        }
    }
    bin_search(l, mid, lef);
    bin_search(mid + 1, r, rig);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin >> n >> m >> q;
    for (int i = 0; i < q; ++i) {
        int a, b;
        cin >> a >> b;
        qry.pb({a, b, i});
    }
    for (int i = 1; i <= n; ++i) {
        dsu.cnt[i] = 1;
        dsu.par[i] = i;
    }
    bin_search(0, m, qry);
    for (int i = 0; i < q; ++i) {
        cout << ans[i] << "\n";
    }
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14