#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 300101
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9
using namespace std;
//using namespace __gnu_pbds;
typedef long double ld;
typedef long long ll;
typedef short int si;
typedef array <int, 2> a2;
//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
ll a, b, cur;
pair <int, int> t[N][20];
int pr[N], rk[N], h[N], logs[N], in[N], tr[N][20], lc;
vector <int> gr;
int fnd(int x) {if (pr[x] != x) pr[x] = fnd(pr[x]); return pr[x];}
void link(int a, int b)
{
if (rk[b] > rk[a]) swap(a, b);
pr[b] = a;
rk[a] += rk[b];
}
vector <pair <int, int> > g[N];
void add(int x, int y, int val)
{
g[x].pb({y, val});
g[y].pb({x, val});
}
void dfs(int v, int p, int val)
{
if (p != -1) h[v] = h[p] + 1;
in[v] = sz(gr);
gr.pb(v);
if (v != 1) t[v][0] = {val, p};
for (auto it : g[v])
{
if (it.F == p) continue;
dfs(it.F, v, it.S);
gr.pb(v);
}
}
int lca(int a, int b)
{
if (in[a] > in[b]) swap(a, b);
int j = logs[in[b] - in[a] + 1];
a = tr[in[a]][j];
b = tr[in[b] - (1 << j) + 1][j];
if (h[a] > h[b]) return b;
return a;
}
int main()
{
//freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m, q;
cin >> n >> m >> q;
for (int i = 2; i < N; i++) logs[i] = logs[i >> 1] + 1;
for (int i = 1; i <= n; i++) {rk[i] = 1; pr[i] = i;}
for (int x = m; x >= 2; x--)
{
if (m / x == 1)
for (int j = 1; j <= n / x; j++)
for (int u = j + 1; u <= n / x; u++)
{
int a = fnd(j * x), b = fnd(u * x);
if (a != b) {add(j * x, u * x, m - x + 1); link(a, b);}
}
else
for (int j = 2; j <= n / x; j++)
{
int a = fnd(j * x), b = fnd(x);
if (a != b) {add(j * x, x, m - x + 1); link(a, b);}
}
}
for (int i = 2; i <= n; i++)
{
int a = fnd(1), b = fnd(i);
if (a != b) {link(a, b); add(1, i, m); }
}
dfs(1, -1, -1);
for (int i = 0; i < sz(gr); i++) tr[i][0] = gr[i];
for (int j = 1; j < 20; j++)
{
for (int i = 1; i <= n; i++)
{
if (h[i] < (1 << j)) continue;
pair <int, int> a = t[i][j - 1];
pair <int, int> b = t[a.S][j - 1];
t[i][j] = {max(a.F, b.F), b.S};
}
for (int i = 0; i < sz(gr); i++)
{
int a = tr[i][j - 1];
int b = tr[min(sz(gr) - 1, i + (1 << (j - 1)))][j - 1];
if (h[a] > h[b]) tr[i][j] = b; else tr[i][j] = a;
}
}
for (; q > 0; q--)
{
int x, y;
cin >> x >> y;
lc = lca(x, y);
int ans = -1;
for (int j = 19; j >= 0; j--)
{
if (h[x] >= (1 << j) && h[x] - (1 << j) >= h[lc])
{
ans = max(ans, t[x][j].F);
x = t[x][j].S;
}
if (h[y] >= (1 << j) && h[y] - (1 << j) >= h[lc])
{
ans = max(ans, t[y][j].F);
y = t[y][j].S;
}
}
cout << ans << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
8704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
8832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
9216 KB |
Output is correct |
| 2 |
Correct |
34 ms |
9088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
9336 KB |
Output is correct |
| 2 |
Correct |
44 ms |
9340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
17276 KB |
Output is correct |
| 2 |
Correct |
48 ms |
17276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
20724 KB |
Output is correct |
| 2 |
Correct |
67 ms |
22384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
26352 KB |
Output is correct |
| 2 |
Correct |
80 ms |
27216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
216 ms |
32368 KB |
Output is correct |
| 2 |
Correct |
124 ms |
35308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
155 ms |
38432 KB |
Output is correct |
| 2 |
Correct |
155 ms |
43760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
172 ms |
46672 KB |
Output is correct |
| 2 |
Correct |
177 ms |
48164 KB |
Output is correct |
