Submission #1165561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165561		ezzatw122	Pictionary (COCI18_pictionary)	C++20	140 / 140	127 ms	6952 KiB

pictionary

#include <bits/stdc++.h>


// you just try again
using namespace std;
#define ll long long

void read() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
}

const int N = 1e5 + 5;

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

    DSU(int n) {
        parent = sz = vector<int>(n);
        for (int i = 0; i < n; ++i) {
            parent[i] = i, sz[i] = 1;
        }
    }

    int find(int n) {
        if (parent[n] == n)return n;
        return parent[n] = find(parent[n]);
    }

    void uni(int x, int y) {
        x = find(x), y = find(y);
        if (x == y)return;
        if (sz[y] > sz[x])swap(x, y);
        parent[y] = x, sz[x] += sz[y];
    }

    bool issame(int x, int y) {
        return find(x) == find(y);
    }
};

int n, m, q, ql[N], qr[N], u[N], v[N], ans[N];

void code() {
    cin >> n >> m >> q;
    for (int i = 0; i < q; ++i) {
        cin >> u[i] >> v[i];
        ql[i] = 1, qr[i] = m;
    }
    bool lassa = 1;
    while (lassa) {
        lassa = 0;
        vector<vector<int>> mids(m + 1);
        DSU dsu(n + 1);
        for (int i = 0; i < q; ++i) {
            if (ql[i] <= qr[i]) {
                lassa = 1;
                mids[(ql[i] + qr[i]) >> 1].push_back(i);
            }
        }
        for (int mid = 1; mid <= m; ++mid) {
            int val = m - mid + 1;
            for (int i = val + val; i <= n; i += val)
                if (i <= n)dsu.uni(val, i);
            for (auto i: mids[mid]) {
                if (dsu.issame(u[i], v[i])) {
                    ans[i] = mid, qr[i] = mid - 1;
                } else {
                    ql[i] = mid + 1;
                }
            }
        }
    }
    for (int i = 0; i < q; ++i) {
        cout << ans[i] << '\n';
    }
}


int main() {
    read();
    int t = 1;
    //  cin >> t;
    while (t--)
        code();
}

• 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