oj.uz

Submission #654606

# Submission time Handle Problem Language Result Execution time Memory
654606 2022-10-31T21:48:21 Z bebra Pictionary (COCI18_pictionary) C++17
14 / 140
 268 ms 35868 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, 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) {
        assert(ans[i] != 1e9);
        cout << ans[i] << '\n';
    }
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 3316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 4660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 5520 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 10364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 13224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 18208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 20140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 187 ms 28276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 35868 KB Output is correct
2 Correct 217 ms 35300 KB Output is correct