Submission #1165179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165179		Siddharth2EEE	Pictionary (COCI18_pictionary)	C++20	140 / 140	124 ms	6812 KiB

pictionary

#include <bits/stdc++.h>
#define lli long long int
#define endl "\n"
#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(__null);

using namespace std;

class DSU {
public:
    int n;
    vector<int> par, sz;

    DSU(int m) {
        n = m;
        par.resize(n), sz.resize(n, 1);
        iota(par.begin(), par.end(), 0);
    }

    int find(int u) {
        if (par[u] == u) return u;
        return par[u] = find(par[u]);
    }

    void merge(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;
        if (sz[v] > sz[u]) swap(u, v);
        par[v] = u, sz[u] += sz[v];
    }
};

signed main() {
    fastio()

    int n, m, q;
    cin >> n >> m >> q;

    vector<array<int, 2>> qr(q);
    for (auto &[a, b] : qr) cin >> a >> b;

    vector<int> lo(q, 1), hi(q, m), ans(q);
    for (int i = 1; i <= 17; i++) {
        vector<int> check[m + 1];
        for (int i = 0; i < q; i++)
            if (lo[i] <= hi[i]) check[(lo[i] + hi[i]) / 2].push_back(i);

        DSU graph(n + 1);
        for (int j = 1; j <= m; j++) {
            int f = m - j + 1;
            for (int k = 2; k * f <= n; k++) graph.merge((k - 1) * f, k * f);
            for (auto &in : check[j]) {
                auto &[a, b] = qr[in];
                if (graph.find(a) == graph.find(b)) ans[in] = j, hi[in] = j - 1;
                else lo[in] = j + 1;
            }
        }
    }

    for (auto &x : ans) cout << x << endl;

    return 0;
}

• 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