Submission #1166015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166015		bluocaroot	Pictionary (COCI18_pictionary)	C++20	140 / 140	169 ms	6956 KiB

pictionary

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using ll = long long;
using namespace std;
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<
        T,
        null_type,
        less<T>,
        rb_tree_tag,
        tree_order_statistics_node_update>;

/*
 * this comment fills you with Determination.
 */
const int N = 1e5 + 7;
int sz[N], par[N];

void init(int n) {
    for (int i = 0; i < n; ++i)
        par[i] = -1, sz[i] = 0;
}

int parent(int u) {
    if (par[u] == -1)
        return u;
    else
        return par[u] = parent(par[u]);
}

bool is_united(int u, int v) {
    u = parent(u);
    v = parent(v);
    return (u == v);
}

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

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#ifdef CAROOT
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int tt = 1;
//    cin >> tt;

    for (int tc = 1; tc <= tt; ++tc) {
        int n, m, q;

        cin >> n >> m >> q;
        vector<pair<int, int>> queries(q);
        for (auto &[a, b]: queries)
            cin >> a >> b;
        vector<int> l(q, 1), r(q, m), ans(q);
        bool lessa = true;
        while (lessa) {
            lessa = false;
            vector<vector<int>> mids(m + 1);
            for (int i = 0; i < q; ++i) {
                if (l[i] <= r[i]) {
                    lessa = true;
                    mids[(l[i] + r[i]) / 2].push_back(i);
                }
            }
            init(n + 1);
            for (int mid = m; mid > 0; --mid) {
                for (int j = mid * 2; j <= n; j += mid)
                    unite(mid, j);
                for (auto i: mids[mid]) {
                    int a = queries[i].first;
                    int b = queries[i].second;
                    if (is_united(a, b))
                        l[i] = mid + 1, ans[i] = m - mid + 1;
                    else
                        r[i] = mid - 1;
                }
            }
        }
        for (auto &i : ans)
            cout << i << '\n';
        cout << '\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