#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, int> pli;
typedef pair <int, ll> pil;
typedef pair <ll, ll> pll;
typedef pair <ld, ld> pdd;
#define cio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define cases int _; cin >> _; while(_--)
#define pb push_back
#define eb emplace_back
#define space << " " <<
#define lb lower_bound
#define ub upper_bound
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define Unique(v) v.erase(unique(all(v)), v.end())
#define mset(x) memset(x, 0, sizeof(x))
#define sflush fflush(stdout)
#define cflush cout.flush()
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define nl cout << "\n";
#define binary(len, num) bitset <len> (num)
#define vt vector
#define ar array
#define Mat vt <vt <int> >
template <typename T> istream& operator >> (istream& in, vector<T>& a) {for(auto &x : a) in >> x; return in;};
template <typename T> ostream& operator << (ostream& out, vector<T>& a) {for(auto &x : a) out << x << ' '; return out;};
int read(){
int w = 1, c, ret;
while((c = getchar()) > '9' || c < '0'){
w = (c == '-' ? -1 : 1);
}
ret = c - '0';
while((c = getchar()) >= '0' && c <= '9'){
ret = ret * 10 + c - '0';
}
return ret * w;
}
int rd(){
int in;
cin >> in;
return in;
}
void write(int x){
if(x < 0){
putchar('-');
x = -x;
}
if(x > 9){
write(x / 10);
}
putchar(x % 10 + '0');
}
const int MAXN = 1e5 + 5, MAXM = 2e5 + 5, INF = 1e9 + 5, MOD = 1e9 + 7;
const ll LINF = 1e18 + 5;
const ld ep = 1e-8, Pi = acos(-1.0);
int n, m, k, x, q;
int a[MAXN];
string s;
int fa[MAXN], rk[MAXN], siz[MAXN];
int find(int x){
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y){
int fx = find(x), fy = find(y);
if(fx == fy){
return;
}
if(rk[fx] > rk[fy]) swap(fx, fy);
fa[fx] = fy;
siz[fy] += siz[fx];
if(rk[fx] == rk[fy]) ++rk[fy];
}
struct edge{
int f, t, val, next;
} e[MAXM];
int head[MAXN], te = 0;
int dep[MAXN];
void add_edge(int u, int v, int w){
e[++te].f = u;
e[te].t = v;
e[te].next = head[u];
e[te].val = w;
head[u] = te;
}
int p[MAXN][20], mx[MAXN][20];
void dfs(int cur){
dep[cur] = dep[p[cur][0]] + 1;
// cout << cur << " " << dep[cur] space dep[p[cur][0]] << "\n";
for(int i = head[cur]; i; i = e[i].next){
int to = e[i].t;
if(to == p[cur][0]) continue;
p[to][0] = cur;
mx[to][0] = e[i].val;
dfs(to);
}
}
int calc(int u, int v){
int ret = 0;
// cout << dep[u] space dep[v] << " ";
if(dep[u] < dep[v]) swap(u, v);
bool flag = (u == 8);
if(dep[u] > dep[v]){
int dif = dep[u] - dep[v];
for(int i = 0; i <= 20; ++i){
if((1 << i) & dif){
ret = max(ret, mx[u][i]);
u = p[u][i];
}
}
}
// cout << u space v << "\n";
if(u == v) return ret;
for(int i = 19; i >= 0; --i){
if(p[u][i] != p[v][i]){
ret = max({ret, mx[u][i], mx[v][i]});
u = p[u][i];
v = p[v][i];
// cout << ret space u space v space i << "\n";
}
}
if(u != v){
ret = max({ret, mx[u][0], mx[v][0]});
}
return ret;
}
void clear(){
}
int main(){
cio;
cin >> n >> m >> q;
iota(fa + 1, fa + n + 1, 1);
generate(rk + 1, rk + n + 1, []{ return 1; });
for(int i = m; i >= 1; --i){
for(int j = i; ; j += i){
if(j + i > n) break;
if(find(j) == find(j + i)) continue;
merge(j, j + i);
add_edge(j, j + i, m - i + 1);
add_edge(j + i, j, m - i + 1);
// cout << j space j + i space m - i + 1 << "\n";
}
}
dfs(1);
int up = log2(n);
for(int i = 1; i <= up; ++i){
for(int j = 1; j <= n; ++j){
p[j][i] = p[p[j][i - 1]][i - 1];
mx[j][i] = max(mx[j][i - 1], mx[p[j][i - 1]][i - 1]);
// cout << p[j][i] << " ";
}
// nl;
}
for(int i = 1; i <= n; ++i){
// cout << i space p[i][0] << "\n";
}
for(int i = 1; i <= q; ++i){
int u = rd(), v = rd();
cout << calc(u, v) << "\n";
}
return 0;
}
Compilation message
pictionary.cpp: In function 'int calc(int, int)':
pictionary.cpp:126:7: warning: unused variable 'flag' [-Wunused-variable]
126 | bool flag = (u == 8);
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
1332 KB |
Output is correct |
| 2 |
Correct |
36 ms |
1244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
1740 KB |
Output is correct |
| 2 |
Correct |
29 ms |
1612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
5684 KB |
Output is correct |
| 2 |
Correct |
21 ms |
5588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
7596 KB |
Output is correct |
| 2 |
Correct |
41 ms |
8396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
10924 KB |
Output is correct |
| 2 |
Correct |
36 ms |
11192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
14244 KB |
Output is correct |
| 2 |
Correct |
88 ms |
16068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
93 ms |
17872 KB |
Output is correct |
| 2 |
Correct |
89 ms |
20080 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
107 ms |
22704 KB |
Output is correct |
| 2 |
Correct |
97 ms |
22496 KB |
Output is correct |
