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>
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
const int N = 100000 + 3;
int n, m, q, x[N], y[N], p[N], ans[N];
set <int> ms[N];
vector <int> qs[N];
void init(){
for (int i = 1; i <= n; i++)
p[i] = i;
}
int get_anc(int x){
if (p[x] == x) return x;
return p[x] = get_anc(p[x]);
}
void unite(int X, int Y, int now){
X = get_anc(X);
Y = get_anc(Y);
if (X == Y) return;
if (ms[X].size() > ms[Y].size()) swap(X, Y);
for (auto u: ms[X]){
for (auto it: qs[u]){
int e = x[it] + y[it] - u;
if (ms[Y].count(e))
ans[it] = now;
}
}
p[X] = Y;
ms[Y].insert(all(ms[X]));
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif // LOCAL
cin >> n >> m >> q;
init();
for (int i = 0; i < q; i++){
cin >> x[i] >> y[i];
qs[x[i]].push_back(i);
qs[y[i]].push_back(i);
}
for (int i = 1; i <= n; i++)
ms[i].insert(i);
int cnt = 1;
for (int i = m; i > 0; i--){
for (int j = i * 2; j <= n; j += i){
unite(j, j - i, cnt);
}
cnt++;
}
// for (auto u: ms[6]) cout << u << " "; cout << "\n";
for (int i = 0; i < q; i++) cout << ans[i] << "\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... |