제출 #1166335

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166335		abdogad	Pictionary (COCI18_pictionary)	C++20	140 / 140	184 ms	7072 KiB

pictionary

#include <bits/stdc++.h>
using namespace std;

// DSU class (provided in the query)
class DSU {
public:
    vector<int> parent;
    vector<int> size;
    int components;
    DSU(int n) {
        parent.resize(n);
        size.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        components = n;
    }
    int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (size[x] < size[y]) {
                swap(x, y);
            }
            parent[y] = x;
            size[x] += size[y];
            components--;
        }
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

vector<pair<int,int>> edges;
vector<int> ans, qs, qe;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;

    qs.resize(q);
    qe.resize(q);
    ans.assign(q, 1);
    for (int i = 0; i < q; i++) {
        cin >> qs[i] >> qe[i]; // Order: x_i, y_i, z_i
        qs[i]--, qe[i]--; // Convert to 0-based indexing
    }

    // Parallel binary search
    vector<int> left(q, 1), right(q, m);
    bool done = true;
    while (done){
        done = false;
        vector<vector<int>> check_at(m + 1); // Queries to check at each K
        for (int i = 0; i < q; i++) {
            if (left[i] <= right[i]) {
                int mid = (left[i] + right[i]) / 2;
                check_at[mid].push_back(i);
                done = true;
            }
        }
        DSU dsu(n); // Initialize DSU with N singletons
        for (int K = m; K > 0; K--) {

            for(int i = K - 1; i + K < n; i += K) {
                dsu.unite(i, i + K);
            }

            for (int i : check_at[K]) {

                int x = qs[i], y = qe[i];
                if (dsu.same(x, y)) {
                    left[i] = K + 1;
                    ans[i] = K;

                } else {
                    right[i] = K - 1;
                }
            }
        }
    }
    // Output results
    for (int i = 0; i < q; i++) {
        cout << m - ans[i] + 1 << endl; // Minimal K for each query
    }

    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