#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 2e5 + 15;
const int LOG = 24;
const int INF = 0x3f3f3f3f;
int n, m, q, pai[MAX], sze[MAX], dp[MAX][LOG], low[MAX][LOG], depth[MAX];
vector<tuple<int, int, int>> edges;
vector<pair<int, int>> adj[MAX];
int find(int u){
return pai[u] = (pai[u] == u ? u : find(pai[u]));
}
bool join(int u, int v){
u = find(u); v = find(v);
if(u == v) return false;
if(sze[v] > sze[u]) swap(u, v);
pai[v] = u; sze[u] += sze[v];
return true;
}
void dfs(int u, int p, int d, int wg){
depth[u] = d; dp[u][0] = p; low[u][0] = wg;
for(auto [v, w] : adj[u]){
if(v == p) continue;
dfs(v, u, d + 1, w);
}
}
int query(int u, int v){
if(depth[u] < depth[v]) swap(u, v);
int ans = INF, k = depth[u] - depth[v];
for(int i = LOG - 1; i >= 0; i--)
if(k & (1 << i)){ ans = min(ans, low[u][i]); u = dp[u][i]; }
if(u == v) return ans;
for(int i = LOG - 1; i >= 0; i--){
if(dp[u][i] != dp[v][i]){
ans = min({ ans, low[u][i], low[v][i] });
u = dp[u][i]; v = dp[v][i];
}
}
ans = min(ans, low[u][0]);
ans = min(ans, low[v][0]);
return ans;
}
int32_t main(void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> q;
for(int i = 1; i <= n; i++){
for(int j = i + i; j <= n; j += i)
edges.emplace_back(i, i, j);
pai[i] = i; sze[i] = 1;
}
sort(edges.begin(), edges.end(), greater<tuple<int, int, int>>());
for(auto [w, u, v] : edges){
if(w > m) continue;
if(join(u, v)){
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
}
dfs(1, 1, 1, INF);
for(int j = 1; j < LOG; j++){
for(int i = 1; i <= n; i++){
dp[i][j] = dp[ dp[i][j - 1] ][j - 1];
low[i][j] = min(low[i][j - 1], low[ dp[i][j - 1] ][ j - 1 ]);
}
}
while(q--){
int u, v; cin >> u >> v;
cout << m - query(u, v) + 1 << '\n';
}
}
Compilation message
pictionary.cpp: In function 'void dfs(int, int, int, int)':
pictionary.cpp:30:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
30 | for(auto [v, w] : adj[u]){
| ^
pictionary.cpp: In function 'int32_t main()':
pictionary.cpp:74:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
74 | for(auto [w, u, v] : edges){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
5076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
5228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
5472 KB |
Output is correct |
| 2 |
Correct |
22 ms |
5540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
5708 KB |
Output is correct |
| 2 |
Correct |
32 ms |
5624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
12856 KB |
Output is correct |
| 2 |
Correct |
34 ms |
12856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
16172 KB |
Output is correct |
| 2 |
Correct |
47 ms |
17852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
21444 KB |
Output is correct |
| 2 |
Correct |
70 ms |
23096 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
28660 KB |
Output is correct |
| 2 |
Correct |
112 ms |
31388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
34544 KB |
Output is correct |
| 2 |
Correct |
155 ms |
38936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
185 ms |
43040 KB |
Output is correct |
| 2 |
Correct |
175 ms |
43140 KB |
Output is correct |
