//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];
}
}
};
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+1][MAX_N], min_edge[LG_N+1][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:79: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:84:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<g[u].size(); ++i) {
~^~~~~~~~~~~~
pictionary.cpp: In member function 'bool disjoint_set::uni(int, int)':
pictionary.cpp:41:2: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
3576 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
3888 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
4612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
5904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
11860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
14824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
107 ms |
19624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
21688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
177 ms |
31268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
181 ms |
38648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
