oj.uz

Submission #575548

# Submission time Handle Problem Language Result Execution time Memory
575548 2022-06-11T00:31:26 Z mmonteiro Pictionary (COCI18_pictionary) C++17
140 / 140
 125 ms 4032 KB 
#include <iostream>
#include <vector>
#include <set>
#include <utility>
#include <algorithm>

#define MAX_VAL 1000000000

class DSU {
    std::vector<int> parent;
    std::vector<int> size;
    std::vector<int> his;
    int n;

public:
    int find(int x, int t) {
        if(x == parent[x]) return x;
        if(his[x] > t) return x;
        return find(parent[x], t);
    }

    void join(int a, int b, int timestamp) {
        a = find(a, MAX_VAL);
        b = find(b, MAX_VAL);
        if(a == b) {
            return;
        }
        if(size[a] > size[b]) {
            std::swap(a, b);
        }
        his[a] = timestamp;
        parent[a] = b;
        size[b] += size[a];
    }

    DSU(int n) {
        this->n = n;
        this->parent.resize(n);
        this->size.resize(n);
        this->his.resize(n);
        for(int i = 0; i < n; ++i) {
            parent[i] = i;
            his[i] = 0;
            size[i] = 1;
        }
    }
};

int main(){

    int n, m, q;

    std::cin >> n >> m >> q;

    std::vector<std::pair<int, int>> cities;

    for(int i = 0; i < q; ++i) {
        int a, b;
        std::cin >> a >> b;
        cities.push_back(std::make_pair(a, b));
    }

    DSU dsu(n + 1);
    for(int g = m, day = 1; g >= 1; --g, day++) {
        for(int j = g; j <= n; j += g) {
            dsu.join(j, g, day);
        }
    }

    std::vector<int> L(q, 0);
    std::vector<int> R(q, m);
    std::vector<int> ans(q, 0);

    while(true) {
        bool ok = false;
        for(int i = 0; i < q; ++i) {
            if(L[i] <= R[i]) {
                ok = true;
                int mid = (L[i] + R[i]) / 2;
                int a = dsu.find(cities[i].first, mid);
                int b = dsu.find(cities[i].second, mid);
                if(a == b) {
                    ans[i] = mid;
                    R[i] = mid - 1;
                } else {
                    L[i] = mid + 1;
                }
            }
        }
        if(!ok) {
            break;
        }
    }

    for(const int &d : ans) {
        std::cout << d << '\n';
    }

    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 676 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 1804 KB Output is correct
2 Correct 43 ms 2024 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 2644 KB Output is correct
2 Correct 61 ms 2560 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1628 KB Output is correct
2 Correct 53 ms 1660 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1848 KB Output is correct
2 Correct 46 ms 1948 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 2400 KB Output is correct
2 Correct 54 ms 2072 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 2984 KB Output is correct
2 Correct 96 ms 3072 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 3460 KB Output is correct
2 Correct 104 ms 3636 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 3944 KB Output is correct
2 Correct 123 ms 4032 KB Output is correct