#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 1e5+5;
const string NAME = "";
int n,m,q,depth[MAXN];
pair<int,int> par[MAXN][20];
vector<pair<int,int>> adj[MAXN];
struct DSU{
int p[MAXN],sz[MAXN];
void init(int n){
iota(p+1,p+n+1,1);
fill(sz+1,sz+n+1,1);
}
int Find(int u){
if(u==p[u]) return u;
return p[u]=Find(p[u]);
}
void Union(int x, int y){
x=Find(x), y=Find(y);
if(x==y) return;
if(sz[x]<sz[y]) swap(x,y);
p[y]=x, sz[x]+=sz[y];
}
}dsu;
void dfs(int u){
for(pair<int,int>& e : adj[u])
if(e.fi!=par[u][0].fi){
depth[e.fi]=depth[u]+1, par[e.fi][0]={u,e.se};
for(int i = 1; i<=__lg(n); ++i){
par[e.fi][i].fi=par[par[e.fi][i-1].fi][i-1].fi;
par[e.fi][i].se=max(par[e.fi][i-1].se,par[par[e.fi][i-1].fi][i-1].se);
}
dfs(e.fi);
}
}
inline int lift(int x, int k){
for(int i = 0; i<=__lg(n); ++i)
if((k>>i)&1) x=par[x][i].fi;
return x;
}
int LCA(int x, int y){
if(depth[x]!=depth[y]){
if(depth[x]<depth[y]) swap(x,y);
x=lift(x,depth[x]-depth[y]);
}
if(x==y) return x;
for(int i = __lg(n); i>=0; --i)
if(par[x][i].fi!=par[y][i].fi) x=par[x][i].fi, y=par[y][i].fi;
return par[x][0].fi;
}
int main()
{
tt;
if(fopen((NAME + ".INP").c_str(), "r")) fo;
cin >> n >> m >> q;
dsu.init(n);
for(int i = m; i>0; --i)
for(int j = i<<1; j<=n; j+=i)
if(dsu.Find(i)!=dsu.Find(j)){
dsu.Union(i,j);
adj[i].pb(j,m-i+1), adj[j].pb(i,m-i+1);
}
dfs(1);
while(q--){
int x,y,lca,rs=0;
cin >> x >> y;
lca=LCA(x,y);
for(int i = __lg(n); i>=0; --i){
if(par[x][i].fi!=0&&depth[par[x][i].fi]>=depth[lca]) rs=max(rs,par[x][i].se), x=par[x][i].fi;
if(par[y][i].fi!=0&&depth[par[y][i].fi]>=depth[lca]) rs=max(rs,par[y][i].se), y=par[y][i].fi;
}
cout << rs << "\n";
}
}
Compilation message (stderr)
pictionary.cpp: In function 'int main()':
pictionary.cpp:3:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pictionary.cpp:71:45: note: in expansion of macro 'fo'
71 | if(fopen((NAME + ".INP").c_str(), "r")) fo;
| ^~
pictionary.cpp:3:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pictionary.cpp:71:45: note: in expansion of macro 'fo'
71 | if(fopen((NAME + ".INP").c_str(), "r")) fo;
| ^~
# | 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... |