제출 #1326076

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326076		ndhn010310	Pictionary (COCI18_pictionary)	C++20	140 / 140	127 ms	15320 KiB

pictionary

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 2e9;

struct DSU {
    vector<int> par, sz;
    
    DSU(int n) {
        par.assign(n+1, 0);
        sz.assign(n+1, 1);
    }
    
    void init() {
        for (int i = 1; i < par.size(); ++i) {
            par[i] = i;
            sz[i] = 1;
        }
    }
    
    int find(int u) {
        return (u==par[u] ? u : par[u] = find(par[u]));
    }
    
    void unite(int u, int v) {
        int a = find(u), b = find(v);
        if (a!=b) {
            if (sz[a]<sz[b]) swap(a, b);
            par[b] = a;
            sz[a] += sz[b];
        }
    }
};

int n, m, q, update;
vector<pair<int, int> > query;
vector<int> ans, ql, qr;
vector<vector<int> > bucket;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> q;
    query.assign(q, make_pair(0, 0));
    for (int i = 0; i < q; ++i) {
        cin >> query[i].first >> query[i].second;
    }
    ql.assign(q, 1); qr.assign(q, m); ans.assign(q, inf);
    bucket.assign(m+1, {});
    DSU dsu(n);
    while (true) {
        update = false;
        for (int i = 1; i <= m; ++i) bucket[i].clear();
        for (int i = 0; i < q; ++i) {
            if (ql[i]<=qr[i]) {
                bucket[(ql[i]+qr[i])/2].emplace_back(i);
                update = true;
            }
        }
        if (!update) break;
        dsu.init();
        for (int i = 1; i <= m; ++i) {
            int gcd = m-i+1;
            for (int j = gcd+gcd; j <= n; j += gcd) {
                dsu.unite(j-gcd, j);
            }
            for (int id : bucket[i]) {
                if (dsu.find(query[id].first)==dsu.find(query[id].second)) {
                    qr[id] = i-1;
                    ans[id] = min(ans[id], i);
                } else ql[id] = i+1;
            }
        }
    }
    for (int i : ans) cout << i << "\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