#include <iostream>
#include <math.h>
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <string.h>
#include <array>
#include <bitset>
#include <time.h>
#include <cstdlib>
using namespace std;
const int maxn=1e5+5, Log=17;
int n, m, q;
pair < int, int > parent[maxn];
int sz[maxn];
vector < pair < int, int > > ms[maxn];
int digni[maxn][Log];
int val[maxn][Log];
int dep[maxn];
int find(int x){
if(parent[x].second==x){
return x;
}
return find(parent[x].second);
}
void update(int x, int y, int val){
x=find(x);
y=find(y);
if(sz[x]>sz[y]){
swap(x, y);
}
parent[x]={val, y};
sz[y]=max(sz[x]+1, sz[y]);
}
bool query(int x, int y){
return find(x)==find(y);
}
void dfs(int x, int prosl, int d){
digni[x][0]=prosl;
dep[x]=d;
for(int i=0; i<ms[x].size(); i++){
if(ms[x][i].first!=prosl){
val[ms[x][i].first][0]=ms[x][i].second;
dfs(ms[x][i].first, x, d+1);
}
}
}
void precompute(){
for(int i=1; i<Log; i++){
for(int j=0; j<n; j++){
digni[j][i]=digni[digni[j][i-1]][i-1];
val[j][i]=max(val[j][i-1], val[digni[j][i-1]][i-1]);
}
}
}
int izjed(int &x, int &y){
int raz=dep[y]-dep[x];
int sol=0;
for(int i=0; i<Log; i++){
if(raz & (1<<i)){
sol=max(sol, val[y][i]);
y=digni[y][i];
}
}
return sol;
}
int lca(int x, int y){
if(dep[x]>dep[y]){
swap(x, y);
}
int sol=izjed(x, y);
if(x==y){
return sol;
}
for(int i=Log-1; i>-1; i--){
if(digni[x][i]!=digni[y][i]){
sol=max(sol, max(val[x][i], val[y][i]));
x=digni[x][i];
y=digni[y][i];
}
}
sol=max(sol, max(val[x][0], val[y][0]));
return sol;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
srand(time(NULL));
cin >> n >> m >> q;
for(int i=1; i<=n; i++){
parent[i]={0, i};
}
int br=1;
for(int i=0; i<m; i++){
for(int j=(m-i)*2; j<=n; j+=m-i){
if(!query(j, j-m+i)){
update(j, j-m+i, br);
}
}
br++;
}
int root;
for(int i=0; i<n; i++){
if(parent[i].second!=i){
ms[i].push_back({parent[i].second, parent[i].first});
ms[parent[i].second].push_back({i, parent[i].first});
}
else{
root=i;
}
}
dfs(root, root, 0);
precompute();
int a, b;
for(int i=0; i<q; i++){
cin >> a >> b;
cout << lca(a, b) << '\n';
}
return 0;
}
Compilation message
pictionary.cpp: In function 'void dfs(int, int, int)':
pictionary.cpp:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<ms[x].size(); i++){
~^~~~~~~~~~~~~
pictionary.cpp: In function 'int main()':
pictionary.cpp:129:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
dfs(root, root, 0);
~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
2816 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
3072 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
3712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
4216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
7672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
9464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
12408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
96 ms |
15548 KB |
Output is correct |
| 2 |
Incorrect |
99 ms |
17144 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
147 ms |
18784 KB |
Output is correct |
| 2 |
Incorrect |
118 ms |
21112 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
149 ms |
23072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
