제출 #1169338

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169338		Amadoo	Pictionary (COCI18_pictionary)	C++20	140 / 140	145 ms	10016 KiB

pictionary

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

#ifdef LOCAL
#include "local_debug.cpp"
#else
#define debug(...)
#define debugArr(...)
#endif

#define int         long long
#define nl          '\n'
#define sp          ' '
#define F           first
#define S           second
#define SZ(s)       (int)((s).size())

const int N = 1e5 + 5;

pair <int, int> queries[N];
int ql[N], qr[N], ans[N];

struct DSU {
    vector <int> par, sz;
    DSU(int n) : par(n + 1), sz(n + 1, 1) {
        for(int i = 1; i <= n; ++i) par[i] = i;
    }
    int get(int v) {
        return (par[v] == v ? v : (par[v] = get(par[v])));
    }
    void unite(int u, int v) {
        u = get(u);
        v = get(v);
        if(u != v) {
            if(sz[u] < sz[v]) swap(u, v);
            par[v] = u;
            sz[u] += sz[v];
        }
    }
    bool query(int u, int v) {
        return get(u) == get(v);
    }
};

void solve() {
    int n, m, q; cin >> n >> m >> q;
    for(int i = 1; i <= q; ++i) cin >> queries[i].F >> queries[i].S;
    for(int i = 1; i <= q; ++i) ql[i] = 1, qr[i] = m;
    while(1) {
        bool done = 1;
        vector <int> qm[m + 1];
        for(int i = 1; i <= q; ++i) {
            if(ql[i] > qr[i]) continue;
            done = 0;
            qm[(ql[i] + qr[i]) >> 1].push_back(i);
        }
        if(done) break;
        DSU dsu(n);
        for(int mid = 1; mid <= m; ++mid) {
            int mult = m - mid + 1;
            for(int i = mult; i <= n; i += mult) dsu.unite(mult, i);
            for(auto i : qm[mid]) {
                auto [u, v] = queries[i];
                if(dsu.query(u, v)) ans[i] = mid, qr[i] = mid - 1;
                else ql[i] = mid + 1;
            }
        }
    }
    for(int i = 1; i <= q; ++i) cout << ans[i] << nl;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int tc = 1;
    // cin >> tc;
    while(tc--) solve();
}

• 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