This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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(size+1)
, m_time(size+1, 0)
, m_size(size+1, 1)
{
for (int i = 0; i <= size; ++i)
m_parent[i] = i;
}
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 = -1;
int l = 0, r = time();
while (l <= r) {
const int m = (l+r)/2;
if (same(a, b, m)) {
ans = m;
r = m-1;
} else {
l = m+1;
}
}
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(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';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |