#include<bits/stdc++.h>
using namespace std ;
const int maxl = 22 ;
const int maxn = 2e5 + 5 ;
int n, m, q ;
int tab[maxl][maxn], mx[maxl][maxn], nivel[maxn] ;
int sz[maxn], pai[maxn] ;
vector<pair<int,int>> grafo[maxn] ;
struct DSU{
int find(int a){return (pai[a] == a ? a : pai[a] = find(pai[a])) ; }
void join(int a, int b){
a = find(a), b = find(b) ;
if(sz[a] > sz[b]) swap(a, b) ;
// tab[0][a] = b ; mx[0][a] = id ; nivel[a] = nivel[b] + 1 ;
sz[b] += sz[a] ; pai[a] = b ;
}
} dsu ;
void dfs(int v, int p){
tab[0][v] = p ;
for(auto a : grafo[v]){
if(a.first == p || nivel[a.first] != -1) continue ;
nivel[a.first] = nivel[v] + 1 ;
mx[0][a.first] = a.second ;
dfs(a.first, v) ;
}
}
int lca(int a, int b){
int ans = 0 ;
if(nivel[a] > nivel[b]) swap(a, b) ;
for(int i = maxl - 1 ; i >= 0 ; i--){
if(tab[i][b] != -1 && nivel[tab[i][b]] >= nivel[a]){
ans = max(ans, mx[i][b]) ;
b = tab[i][b] ;
}
}
if(a == b) return ans ;
for(int i = maxl - 1 ; i >= 0 ; i--){
if(tab[i][a] != -1 && tab[i][b] != -1 && tab[i][a] != tab[i][b]){
ans = max({mx[i][a], ans, mx[i][b]}) ;
b = tab[i][b], a = tab[i][a] ;
}
}
return max({ans, mx[0][a], mx[0][b]}) ;
}
int main(){
ios_base::sync_with_stdio(false) ; cin.tie(NULL) ;
cin >> n >> m >> q ;
for(int i = 1 ; i <= n ; i++) pai[i] = i, sz[i] = 1, nivel[i] = -1 ;
for(int i = 1 ; i < maxl ; i++){
for(int j = 1 ; j <= n ; j++){
tab[i][j] = -1 ;
}
}
for(int md = m ; md > 0 ; md--){
for(int id = md + md ; id <= n ; id += md){
if(dsu.find(md) == dsu.find(id)) continue ;
grafo[md].push_back({id, m - md + 1}) ; grafo[id].push_back({md, m - md + 1}) ;
dsu.join(md, id) ;
}
}
nivel[1] = 0 ;
dfs(1, 0) ;
for(int i = 1 ; i < maxl ; i++){
for(int j = 1 ; j <= n ; j++){
if(tab[i-1][j] == -1) continue ;
mx[i][j] = max(mx[i-1][j], mx[i-1][tab[i-1][j]]) ;
tab[i][j] = tab[i-1][tab[i-1][j]] ;
}
}
for(int i = 1 ; i <= q ; i++){
int a, b ; cin >> a >> b ;
cout << lca(a, b) << "\n" ;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
5636 KB |
Output is correct |
| 2 |
Correct |
23 ms |
6188 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
5852 KB |
Output is correct |
| 2 |
Correct |
31 ms |
6476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
10324 KB |
Output is correct |
| 2 |
Correct |
32 ms |
10912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
12436 KB |
Output is correct |
| 2 |
Correct |
32 ms |
14000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
15712 KB |
Output is correct |
| 2 |
Correct |
51 ms |
16820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
19468 KB |
Output is correct |
| 2 |
Correct |
86 ms |
20964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
22816 KB |
Output is correct |
| 2 |
Correct |
94 ms |
26624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
27876 KB |
Output is correct |
| 2 |
Correct |
127 ms |
29200 KB |
Output is correct |
