oj.uz

Submission #654775

# Submission time Handle Problem Language Result Execution time Memory
654775 2022-11-01T15:18:18 Z bebra Pictionary (COCI18_pictionary) C++17
140 / 140
 202 ms 37016 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3284 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3848 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5456 KB Output is correct
2 Correct 18 ms 5664 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6688 KB Output is correct
2 Correct 25 ms 6132 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 11136 KB Output is correct
2 Correct 57 ms 11092 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 14172 KB Output is correct
2 Correct 65 ms 14160 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 19164 KB Output is correct
2 Correct 77 ms 19308 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 21200 KB Output is correct
2 Correct 132 ms 26604 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 29408 KB Output is correct
2 Correct 170 ms 32904 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 37016 KB Output is correct
2 Correct 198 ms 36544 KB Output is correct