#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
typedef pair<int, int> pii;
int ini[maxn], fim[maxn], n, m, q;
int pai[maxn], sz[maxn];
pii query[maxn];
vector<int> v[maxn];
int Find(int x)
{
if (pai[x] == x) return x;
return pai[x] = Find(pai[x]);
}
void Join(int x, int y)
{
x = Find(x), y = Find(y);
if (x == y) return;
if (sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y], pai[y] = x;
}
void init(void)
{
for (int i = 1; i <= m; i++)
v[i].clear();
for (int i = 1; i <= n; i++)
pai[i] = i, sz[i] = 1;
}
void solve(void)
{
bool flag = 1;
while (flag)
{
init();
flag = 0;
for (int i = 1; i <= q; i++)
{
if (ini[i] != fim[i])
{
int mid = (ini[i]+fim[i])/2;
v[mid].push_back(i), flag = 1;
}
}
for (int i = 1; i <= m; i++)
{
int d = m-i+1;
for (int j = d; j <= n; j += d)
Join(d, j);
for (auto x: v[i])
{
if (Find(query[x].first) == Find(query[x].second)) fim[x] = i;
else ini[x] = i+1;
}
}
}
}
int main(void)
{
cin >> n >> m >> q;
for (int i = 1; i <= q; i++)
{
cin >> query[i].first >> query[i].second;
ini[i] = 1, fim[i] = m;
}
solve();
for (int i = 1; i <= q; i++)
cout << fim[i] << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
3064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
3836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
6852 KB |
Output is correct |
2 |
Correct |
62 ms |
6852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
91 ms |
8528 KB |
Output is correct |
2 |
Correct |
81 ms |
8528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
102 ms |
8528 KB |
Output is correct |
2 |
Correct |
97 ms |
8528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
129 ms |
8528 KB |
Output is correct |
2 |
Correct |
93 ms |
8528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
191 ms |
10148 KB |
Output is correct |
2 |
Correct |
158 ms |
10148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
121 ms |
10148 KB |
Output is correct |
2 |
Correct |
248 ms |
11448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
298 ms |
13076 KB |
Output is correct |
2 |
Correct |
294 ms |
13076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
407 ms |
15172 KB |
Output is correct |
2 |
Correct |
398 ms |
15172 KB |
Output is correct |