Submission #654775

#	Time	Username	Problem	Language	Result	Execution time	Memory
654775		bebra	Pictionary (COCI18_pictionary)	C++17	140 / 140	202 ms	37016 KiB

pictionary

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

#define dbg(x) cerr << #x << ": " << x << endl;


const int MAX_N = 1e5 + 5;
const int MAX_Q = 1e5 + 5;
vector<pair<int, int>> queries[MAX_N];
int ans[MAX_Q];

struct DisjointSetUnion {
    vector<int> parent;
    vector<unordered_set<int>> sets;
    vector<int> size;
    
    DisjointSetUnion(int n) {
        parent.resize(n);
        sets.resize(n);
        size.resize(n);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
            sets[i].insert(i);
            size[i] = queries[i].size() + 1;
        }
    }

    int find(int v) const {
        return parent[v];
    }

    void unite(int u, int v, int days_n) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        if (size[u] > size[v]) {
            swap(u, v);
        }
        size[v] += sets[u].size();
        for (auto x : sets[u]) {
            vector<pair<int, int>> keep;
            for (auto [y, idx] : queries[x]) {
                if (find(y) == v) {
                    ans[idx] = min(ans[idx], days_n);
                    --size[v];
                } else if (find(y) != u) {
                    keep.emplace_back(y, idx);
                }
            }
            swap(queries[x], keep);
            size[v] += keep.size();
            parent[x] = v;
            sets[v].insert(x);
        }
    }
};


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < q; ++i) {
        int u, v;
        cin >> u >> v;
        queries[u].emplace_back(v, i);
        queries[v].emplace_back(u, i);
    }
    DisjointSetUnion dsu(n + 5);
    fill_n(ans, MAX_N, 1e9);
    for (int g = m; g >= 1; --g) {
        int u = g;
        for (int v = 2 * g; v <= n; v += g) {
            dsu.unite(u, v, m - g + 1);
            u = v;
        }
    }
    for (int i = 0; i < q; ++i) {
        cout << ans[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