Submission #575548

#	Time	Username	Problem	Language	Result	Execution time	Memory
575548		mmonteiro	Pictionary (COCI18_pictionary)	C++17	140 / 140	125 ms	4032 KiB

pictionary

#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 / 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