//I love armpit fetish
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"
const int MAX_N = 100002;
const int LG_N = 19;
const int INF = 1e9;
class disjoint_set {
public:
int lab[MAX_N];
disjoint_set() {
memset(lab, 0, sizeof(lab));
}
int findset(int u) {
return lab[u]<=0 ? u : lab[u] = findset(lab[u]);
}
bool uni(int s, int t) {
s = findset(s);
t = findset(t);
if (s==t)
return false;
if (lab[s]<lab[t])
lab[t] = s;
else if (lab[s]>lab[t])
lab[s] = t;
else {
lab[s] = t;
--lab[t];
}
return true;
}
};
struct edge {
int u, v, w;
edge() {}
edge(int u, int v, int w):
u(u), v(v), w(w) {}
bool operator<(const edge &E) {
return w > E.w;
}
};
int n, m, nQuery, p[LG_N+2][MAX_N], min_edge[LG_N+2][MAX_N], l[MAX_N];
vector<edge> e;
vector<pair<int, int> > g[MAX_N];
disjoint_set dsu;
void sieve() {
for (int i=1; i<=m; ++i) {
for (int j=2*i; j<=n; j += i)
e.push_back(edge(i, j, i));
}
}
void process_edge(edge e) {
if (dsu.uni(e.u, e.v)) {
g[e.u].push_back(make_pair(e.v, e.w));
g[e.v].push_back(make_pair(e.u, e.w));
}
}
void build_MST() {
sort(e.begin(), e.end());
// for (int i=0; i<e.size(); ++i)
// cerr << e[i].u << ' ' << e[i].v << ' ' << e[i].w << '\n';
for (int i=0; i<e.size(); ++i)
process_edge(e[i]);
}
void fix_root(int u) {
for (int i=0; i<g[u].size(); ++i) {
int v = g[u][i].first, w = g[u][i].second;
if (v!=p[0][u]) {
p[0][v] = u;
min_edge[0][v] = w;
l[v] = l[u] + 1;
fix_root(v);
}
}
}
void init_lca() {
for (int i=1; i<=LG_N; ++i) {
for (int j=1; j<=n; ++j) {
p[i][j] = p[i-1][p[i-1][j]];
min_edge[i][j] = min(min_edge[i-1][j], min_edge[i-1][p[i-1][j]]);
}
}
}
int get_min(int x, int y) {
int res = INF;
for (int k=LG_N; k>=0; --k) {
if (l[p[k][x]]>=l[y]) {
res = min(res, min_edge[k][x]);
x = p[k][x];
}
}
for (int k=LG_N; k>=0; --k) {
if (l[p[k][y]]>=l[x]) {
res = min(res, min_edge[k][y]);
y = p[k][y];
}
}
for (int k=LG_N; k>=0; --k) {
if (p[k][x]!=p[k][y]) {
res = min(res, min(min_edge[k][x], min_edge[k][y]));
x = p[k][x];
y = p[k][y];
}
}
while (x!=y) {
res = min(res, min(min_edge[0][x], min_edge[0][y]));
x = p[0][x];
y = p[0][y];
}
return res;
}
void solve_query() {
while (nQuery--) {
int u, v;
cin >> u >> v;
cout << m - get_min(u, v) + 1 << '\n';
}
}
int main() {
//#define OFFLINE_JUDGE doraemon
#ifdef OFFLINE_JUDGE
freopen(FILE_NAME".inp", "r", stdin);
freopen(FILE_NAME".out", "w", stdout);
#endif
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> nQuery;
sieve();
build_MST();
l[1] = 1;
fix_root(1);
init_lca();
solve_query();
}
Compilation message
pictionary.cpp: In function 'void build_MST()':
pictionary.cpp:80:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<e.size(); ++i)
~^~~~~~~~~
pictionary.cpp: In function 'void fix_root(int)':
pictionary.cpp:85:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<g[u].size(); ++i) {
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
3448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
3592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
3932 KB |
Output is correct |
| 2 |
Correct |
35 ms |
4448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
5016 KB |
Output is correct |
| 2 |
Correct |
55 ms |
5592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
12144 KB |
Output is correct |
| 2 |
Correct |
71 ms |
12472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
15560 KB |
Output is correct |
| 2 |
Correct |
82 ms |
16716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
20852 KB |
Output is correct |
| 2 |
Correct |
89 ms |
22292 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
23364 KB |
Output is correct |
| 2 |
Correct |
171 ms |
30284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
189 ms |
33004 KB |
Output is correct |
| 2 |
Correct |
243 ms |
37676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
280 ms |
41520 KB |
Output is correct |
| 2 |
Correct |
313 ms |
42604 KB |
Output is correct |
