#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int maxn = 1e5 + 5;
int sz[maxn], par[maxn], edge[maxn];
int N, M, Q;
void init(int n)
{
for(int i = 1; i <= n; ++i){
sz[i] = 1;
par[i] = i;
edge[i] = 1e9;
}
}
int finds(int u)
{
if(par[u] == u) return u;
return par[u] = finds(par[u]);
}
void merges(int u, int v, int w)
{
u = finds(u); v = finds(v);
if(u == v) return;
if(sz[u] < sz[v]) swap(u, v);
par[v] = u;
edge[v] = u;
sz[u] += sz[v];
}
int path(int u, int v)
{
int ans = 0;
while(u != v){
//cerr << u << ' ' << v << '\n';
if(edge[u] < edge[v]){
ans = max(ans, edge[u]);
u = par[u];
}
else{
ans = max(ans, edge[v]);
v = par[v];
}
}
return ans;
}
signed main(void)
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("A.INP", "r", stdin);
freopen("A.OUT", "w", stdout);
#endif // LOCAL
cin >> N >> M >> Q;
init(N);
for(int i = M; i >= 1; --i){
for(int j = i; j <= N; j += i){
merges(i, j, M - i + 1);
}
}
while(Q--){
int u, v; cin >> u >> v;
cout << path(u, v) << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
640 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
22 ms |
1280 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
37 ms |
1664 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
20 ms |
1408 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
23 ms |
1536 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
31 ms |
2168 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
35 ms |
2520 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
47 ms |
2936 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
49 ms |
3448 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |