#include <bits/stdc++.h>
#define fi first
#define se second
#define bupo __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e5+5;
int N, M, Q, A[MAXN], B[MAXN];
int P, L[MAXN], R[MAXN], ans[MAXN], par[MAXN];
vector <int> mid[MAXN];
vector <pii> edge[MAXN];
int find(int x) {
if (par[x] == x) return x;
return par[x] = find(par[x]);
}
void join(int x,int y) {
x = find(x);
y = find(y);
par[x] = y;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M >> Q;
for (int i=1;i<=N;i++) {
par[i] = i;
}
for (int i=M;i>1;i--) {
for (int j=2*i;j<=N;j+=i) {
if (find(i) != find(j)) {
join(i,j);
edge[M+1-i].push_back({i,j});
}
}
}
for (int i=1;i<=Q;i++) {
cin >> A[i] >> B[i];
L[i] = 1;
R[i] = M-1;
ans[i] = M;
if (L[i] <= R[i]) {
mid[(L[i]+R[i])/2].push_back(i);
}
else {
P++;
}
}
while (P < Q) {
for (int i=1;i<=N;i++) {
par[i] = i;
}
for (int i=1;i<M;i++) {
for (pii x : edge[i]) {
join(x.fi,x.se);
}
for (int j : mid[i]) {
if (find(A[j]) == find(B[j])) {
ans[j] = i;
R[j] = i - 1;
}
else {
L[j] = i + 1;
}
if (L[j] <= R[j]) {
mid[(L[j]+R[j])/2].push_back(j);
}
else {
P++;
}
}
mid[i].clear();
}
}
for (int i=1;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... |