Submission #1276522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276522		MinhKien	Pictionary (COCI18_pictionary)	C++20	140 / 140	214 ms	29240 KiB

pictionary

#include <iostream>
#include <vector>
#include <set>

using namespace std;

const int N = 1e5 + 10;
int n, m, k, fi[N];
set <int> vis;
vector <int> v[N], queries[N];

struct query {
    int x, y, l, r, ans;
} q[N];

struct DSU {
    int par[N];

    int FindPar(int u) {
        return par[u] < 0 ? u : par[u] = FindPar(par[u]);
    }

    void unite(int x, int y) {
        x = FindPar(x);
        y = FindPar(y);

        if (x == y) return;

        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
    }

    void reset() {
        for (int i = 1; i <= n; ++i) par[i] = -1;
    }

    bool same(int x, int y) {
        return FindPar(x) == FindPar(y);
    }
} dsu;

int main() {
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n >> m >> k;
    for (int i = 1; i <= k; ++i) {
        cin >> q[i].x >> q[i].y;
        if (q[i].x == q[i].y) {
            q[i].ans = 0;
            q[i].l = m; q[i].r = -1;
        } else {
            q[i].l = q[i].ans = 1;
            q[i].r = m;
        }
    }

    for (int i = m; i >= 1; --i) {
        vis.clear();
        for (int j = i; j <= n; j += i) {
            if (fi[j] && vis.find(fi[j]) == vis.end()) {
                vis.insert(fi[j]);
                v[i].push_back(j);
            } else {
                if (!fi[j]) {
                    fi[j] = i;
                    v[i].push_back(j);
                }
            }
        }
    }

    while (true) {
        bool ck = false;
        for (int i = 1; i <= k; ++i) {
            if (q[i].l > q[i].r) continue;
            queries[(q[i].l + q[i].r) >> 1].push_back(i);
            ck = true;
        }

        if (!ck) break;

        dsu.reset();
        for (int i = m; i >= 1; --i) {
            for (int j = 1; j < v[i].size(); ++j) dsu.unite(v[i][j], v[i][j - 1]);

            for (int z: queries[i]) {
                if (dsu.same(q[z].x, q[z].y)) {
                    q[z].ans = i;
                    q[z].l = i + 1;
                } else {
                    q[z].r = i - 1;
                }
            }
            queries[i].clear();
        }
    }

    for (int i = 1; i <= k; ++i) {
        if (q[i].ans == 0) cout << "0\n";
        else cout << m - q[i].ans + 1 << "\n";
    }

    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