#include<bits/stdc++.h>
using namespace std;
void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
cerr << h; if(sizeof...(t)) cerr << ", ";
DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL
#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"
using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;
void setIO(string NAME = "") {
cin.tie(0)->sync_with_stdio(0);
if(sz(NAME)) {
freopen((NAME + ".inp").c_str(),"r",stdin);
freopen((NAME + ".out").c_str(),"w",stdout);
}
}
tcT> bool ckmin(T&a, const T&b) {
return b < a ? a=b,1 : 0; }
tcT> bool ckmax(T&a, const T&b) {
return b > a ? a=b,1 : 0; }
const int MOD = 1e9 + 7;
struct UF {
vi e;
void init(int n) { e.assign(n, -1); }
int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
bool join(int a, int b) {
a = find(a), b = find(b);
if(a == b) return false;
if(e[a] > e[b]) swap(a,b);
e[a] += e[b]; e[b] = a;
return true;
}
};
const int MX = 1e5+5, LG = 19;
int N, M, Q;
UF dsu;
V<pi> adj[MX];
int par[MX][LG], minInd[MX][LG], dep[MX];
void dfs(int u, int p) {
each(ed, adj[u]) if(ed.first != p) {
int v = ed.first, w = ed.second;
dep[v] = dep[par[v][0] = u] + 1;
minInd[v][0] = w;
dfs(v, u);
}
}
int query(int u, int v) {
if(dep[u] < dep[v]) swap(u,v);
int ans = MOD;
int d = dep[u] - dep[v];
R0F(i,LG) if(d>>i&1) {
ckmin(ans, minInd[u][i]);
u = par[u][i];
}
if(u == v) return ans;
R0F(i,LG) if(par[u][i] != par[v][i]) {
ckmin(ans, min(minInd[u][i], minInd[v][i]));
u = par[u][i];
v = par[v][i];
}
return min({ans, par[u][0], par[v][0]});
}
void solve() {
cin>>N>>M>>Q;
dsu.init(N+5);
ROF(i,1,M+1) {
for(int j = i*2; j<=N; j+=i) {
if(dsu.join(i, j)) {
adj[i].pb({j, i});
adj[j].pb({i, i});
}
}
}
par[1][0] = 1;
minInd[1][0] = MOD;
dfs(1, -1);
FOR(j,1,LG) FOR(i,1,N+1) {
par[i][j] = par[par[i][j-1]][j-1];
minInd[i][j] = min(minInd[i][j-1], minInd[par[i][j-1]][j-1]);
}
while(Q-->0) {
int u,v;
cin>>u>>v;
cout << M-query(u,v)+1 << nl;
}
}
int main() {
setIO();
int t=1;
//cin>>t;
while(t-->0) {
solve();
}
return 0;
}
Compilation message
pictionary.cpp: In function 'void setIO(std::string)':
pictionary.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | freopen((NAME + ".inp").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pictionary.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | freopen((NAME + ".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
3668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
4104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
7764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
9556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
61 ms |
12680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
16276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
19300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
117 ms |
23796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
