oj.uz

Submission #94204

# Submission time Handle Problem Language Result Execution time Memory
94204 2019-01-16T16:23:25 Z johnjq Pictionary (COCI18_pictionary) C++17
140 / 140
 507 ms 53484 KB 
#include <bits/stdc++.h>
using namespace std;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> ii;
/////////////////////////////////////////////////////// BEGIN OF UNION-FIND WITH PARTIAL PERSISTENCY ///////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////
//////////////// Note: this class supports both 0-indexed and 1-indexed elements ////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////
class UnionFindPartial {
private:
    int m_current_time;
    std::vector<int> m_parent; // [0 .. size]
    std::vector<int> m_time;   // [0 .. size]
    std::vector<int> m_size;   // [0 .. size]
public:
    UnionFindPartial(const int size) {
        m_current_time = 0;
        m_parent.reserve(size+1);
        m_time.reserve(size+1);
        m_size.reserve(size+1);
        for (int i = 0; i <= size; ++i) {
            m_parent.push_back(i);
            m_time.push_back(0);
            m_size.push_back(1);
        }
    }
    inline int time() const {
        return m_current_time;
    }
    inline int find(int x, const int last_time) const {
        while (m_time[x] <= last_time && x != m_parent[x])
            x = m_parent[x];
        return x;
    }
    inline int find(const int x) const {
        return find(x, time());
    }
    void merge(const int a, const int b) {
        const int gpa = find(a);
        const int gpb = find(b);
        m_current_time += 1;
        if (gpa != gpb) {
            if (m_size[gpa] < m_size[gpb]) {
                m_parent[gpa] = gpb;
                m_time[gpa] = m_current_time;
                m_size[gpb] += m_size[gpa];
            } else {
                m_parent[gpb] = gpa;
                m_time[gpb] = m_current_time;
                m_size[gpa] += m_size[gpb];
            }
        }
    }
    bool same(const int a, const int b) {
        return find(a) == find(b);
    }
    bool same(const int a, const int b, const int last_time) {
        return find(a, last_time) == find(b, last_time);
    }
    inline int find_time(int a, int b) {
        int ans = 0;
        while (a != b) {
            //cout<<"a"<<endl;
            if (m_parent[a] == a && m_parent[b] == b) break;
            //printf("%d %d %d %d\n", a, b, m_parent[a], m_parent[b]);
            if ((m_time[a] <= m_time[b] && m_parent[a] != a) || m_parent[b] == b) {
                ans = max(ans, m_time[a]);
                a = m_parent[a];
            } else {
                ans = max(ans, m_time[b]);
                b = m_parent[b];
            }
        }
        return ans;
    }
    int size(const int a) {
        const int gpa = find(a);
        return m_size[gpa];
    }
};
/////////////////////////////////////////////////////// END OF UNION-FIND WITH PARTIAL PERSISTENCY ///////////////////////////////////////////////////////
 
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int n, m, q;
    cin>>n>>m>>q;
    UnionFindPartial uf(2*n);
    map<int, int> ans;
    ans[uf.time()] = 0;
    for (int day = m; day >= 1; --day) {
        for (int i = 2; i*day <= n; ++i) {
            uf.merge(day, i*day);
            ans[uf.time()] = m-day+1;
        }
    }
    while (q--) {
        int a, b;
        cin>>a>>b;
        int time = uf.find_time(a, b);
        cout<<ans[time]<<'\n';
    }
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 504 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 760 KB Output is correct
2 Correct 24 ms 732 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1112 KB Output is correct
2 Correct 31 ms 1016 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 10640 KB Output is correct
2 Correct 85 ms 10588 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 15352 KB Output is correct
2 Correct 116 ms 13972 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 23056 KB Output is correct
2 Correct 181 ms 24456 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 17588 KB Output is correct
2 Correct 293 ms 35896 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 40892 KB Output is correct
2 Correct 426 ms 45612 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 53484 KB Output is correct
2 Correct 485 ms 52076 KB Output is correct