Submission #1326532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326532		lknijikaijichi	Pictionary (COCI18_pictionary)	C++20	140 / 140	161 ms	7040 KiB

pictionary

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

constexpr int vsz = 1e5 + 5;

#define all(v) v.begin(), v.end()
#define ll long long
#define endl "\n"

template <typename T>
using vec = vector<T>;

int n, m, q, l[vsz], r[vsz], ans[vsz];

struct query {
    int a, b;
} queries[vsz];

struct DSU {
    vec<int> par;
    vec<int> sz;
    DSU(int n) {
        init(n);
    }

    inline void init(int n) {
        sz.assign(n + 1, 1);
        par.resize(n + 1);
        for (int i = 1; i <= n; ++i) {
            par[i] = i;
        }
    }

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


    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        
        par[b] = a;
        
        sz[a] += sz[b];
    }
};

void solve() {
    cin >> n >> m >> q;

    for (int i = 1; i <= q; ++i) {
        cin >> queries[i].a >> queries[i].b;
        l[i] = 0;
        r[i] = m + 1;
        ans[i] = -1;
    }

    while (true) {
        bool fault = false;

        vec<vec<int>> bucket(m + 1);

        for (int i = 1; i <= q; ++i) {
            if (l[i] + 1 >= r[i]) {
                continue;
            }

            fault = true;

            bucket[(l[i] + r[i]) >> 1].push_back(i);
        }

        if (!fault) break;

        DSU dsu(n);

        for (int i = m; i >= 1; --i) {

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

            for (auto& j : bucket[m - i + 1]) {
                int a = queries[j].a;
                int b = queries[j].b;

                if(dsu.find(a) == dsu.find(b)) {
                    ans[j] = m - i + 1;
                    r[j] = m - i + 1;
                }
                else {
                    l[j] = m - i + 1;
                }
            }
        }
    }

    for(int i = 1; i <= q; ++i) {
        cout << ans[i] << endl;
    }
}

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

    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