#include <bits/stdc++.h>
#include <functional>
#include <vector>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int MAX_N = 1e5 + 42;
const int INF = 1e9;
const int mod = 1e9 + 7;
int par[MAX_N];
int sz[MAX_N];
int get( int x ){ return par[x] = ( x == par[x] ? x : get(par[x]) ); }
void uni( int a, int b ){
a = get(a);
b = get(b);
if( a == b ) return;
if( sz[a] > sz[b] ){
par[b] = a;
sz[a] += sz[b];
}else{
par[a] = b;
sz[b] += sz[a];
}
}
std::vector<std::pair<int, int>> v[MAX_N];
int lca[MAX_N][30];
int maxLca[MAX_N][30];
bool viz[MAX_N];
int dep[MAX_N];
void dfs( int x ){
viz[x] = true;
for( auto j : v[x] ){
if( !viz[j.first] ){
dep[j.first] = dep[x] + 1;
lca[j.first][0] = x;
maxLca[j.first][0] = j.second;
dfs( j.first );
}
}
}
ll st;
int getLca( int a, int b ){
if( dep[a] > dep[b] ) std::swap( a, b );
int diff = dep[b] - dep[a];
for( int i = st-1 ; i>=0 ; i-- ){
if( (1<<i)&diff ){
b = lca[b][i];
}
}
if( a == b ) return a;
for( int i=st-1 ; i>=0 ; i-- ){
if( lca[a][i] != lca[b][i] ){
a = lca[a][i];
b = lca[b][i];
}
}
return lca[a][0];
}
ll getMax( int a, int b ){
int nas = -INF;
for( int i = st-1 ; i>=0 ; i-- ){
if( dep[a] - dep[b] >= (1<<i)){
nas = std::max( nas, maxLca[a][i] );
a = lca[a][i];
}
}
return nas;
}
int main () {
std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
int n, m, q;
std::cin>>n>>m>>q;
for( int i=0 ; i<=n ; i++ ){par[i] = i; sz[i] =1;}
for( int i=m ; i>=1 ; i-- ){
int a = i;
// std::cerr<<i<<" , "<<m-i+1<<":\n";
for( int j=2 ; i*j <= n ; j++ ){
int b = i*j;
if( get( a ) != get(b) ){
// std::cerr<<a<<" -> "<<b<<"\n";
uni(a, b);
v[a].push_back({b, m-i+1});
v[b].push_back({a, m-i+1});
}
}
// std::cerr<<"\n";
}
dfs( 1 );
st = 0;
while( true ){
st++;
if( (1<<st) > n ) break;
for( int i=1 ; i<=n ; i++ ){
lca[i][st] = lca[lca[i][st-1]][st-1];
maxLca[i][st] = std::max( maxLca[lca[i][st-1]][st-1], maxLca[i][st-1]);
}
}
while( q-- ){
int a, b;
std::cin>>a>>b;
int lc = getLca( a, b );
// std::cerr<<" ! "<<lc<<"\n";
ll nas = std::max( getMax( a, lc ), getMax( b, lc ) );
std::cout<<nas<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
3028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
3660 KB |
Output is correct |
| 2 |
Correct |
26 ms |
3648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
4152 KB |
Output is correct |
| 2 |
Correct |
32 ms |
4040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
9696 KB |
Output is correct |
| 2 |
Correct |
32 ms |
9700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
12400 KB |
Output is correct |
| 2 |
Correct |
58 ms |
13708 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
16908 KB |
Output is correct |
| 2 |
Correct |
63 ms |
17428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
21880 KB |
Output is correct |
| 2 |
Correct |
100 ms |
23908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
126 ms |
26424 KB |
Output is correct |
| 2 |
Correct |
120 ms |
29784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
156 ms |
32844 KB |
Output is correct |
| 2 |
Correct |
139 ms |
33016 KB |
Output is correct |
