제출 #1325621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1325621		sashimivssushi	Pictionary (COCI18_pictionary)	C++20	140 / 140	128 ms	14892 KiB

pictionary

#include <bits/stdc++.h>
#include <random>
#include <chrono>
#define ll long long
#define db double
#define sti string
#define vt vector
#define INF ((int) 1e9)
#define MOD 1000000007
#define BASE 311
#define pii pair<int, int>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define pdd pair<db, db>
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << #x << " = " << x << '\n';
#define bit(mask, i) ((mask >> i) & 1)
#define fi first
#define sc second

using namespace std;

const sti name = "";
const int MAXN = 1e6;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

inline void file () {
    freopen ((name + ".inp").c_str (), "r", stdin);
    freopen ((name + ".out").c_str (), "w", stdout);
}

struct DSU {
    vt<int> par, sz;
    DSU () = default;
    DSU (int n) : par (n), sz (n) {
        init();
    }

    void init () {
        iota(all(par), 0);
        fill(all(sz), 1);
    }

    int find (int u) {
        return u == par[u] ? u : par[u] = find (par[u]);
    }

    bool unite (int u, int v) {
        u = find (u);
        v = find (v);
        if (u == v) return false;
        if (sz[u] < sz[v]) swap (u, v);
        par[v] = u;
        sz[u] += sz[v];
        sz[v] = 0;
        return true;
    }
};

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

    int n, m, q; cin >> n >> m >> q;
    vt<pii> queries(q);
    vt<int> left(q, 1), right(q, m);
    for (auto& Q : queries)
        cin >> Q.fi >> Q.sc;
    vt<vt<int>> cand;
    DSU g(n + 1);
    while (true) {
        cand.assign(m + 1, vt<int>());
        g.init();
        bool any = false;
        for (int i = 0; i < q; ++i) {
            if (left[i] >= right[i]) continue;
            int mid = (left[i] + right[i]) >> 1;
            cand[mid].emplace_back(i);
            any = true;
        }
        if (!any) break;
        for (int mid = 1; mid <= m; ++mid) {
            int step = m - mid + 1;
            for (int i = 2 * step; i <= n; i += step)
                g.unite(i, i - step);
            for (int& i : cand[mid]) {
                auto& [u, v] = queries[i];
                if (g.find(u) == g.find(v)) right[i] = mid;
                else left[i] = mid + 1;
            }
        }
    }
    for (int& l : left) cout << l << '\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