#include<bits/stdc++.h>
using namespace std;
pair<int ,int> par[100005];
int sz[100005];
// tree after dsu first int is edge, second is weight
vector<pair<int ,int>> graph[100005];
int maxs[100005][30];
int parent[100005][30];
bool visited[100005];
int h[100005];
void construct(int n)
{
for(int i = 0; i <=n; i ++)
{
par[i].first = i;
sz[i] = 1;
}
}
int find(int a)
{
if(par[a].first !=a)
{
return find(par[a].first);
}
return a;
}
void unite(int x, int y, int w)
{
int a = find(x);
int b = find(y);
if(a!=b)
{
if(sz[a] > sz[b])
{
swap(a, b);
}
par[a] = {b, w};
sz[b] +=sz[a];
graph[b].push_back({a, w});
graph[a].push_back({b, w});
}
}
void dfs(int u )
{
visited[u] = true;
for(auto v:graph[u])
{
if(!visited[v.first])
{
parent[v.first][0] = u;
maxs[v.first][0] = v.second;
h[v.first] = h[u] - 1;
dfs(v.first);
}
}
}
int findmin(int x, int y)
{
int ans = 0;
if(h[x] < h[y])
{
swap(x, y);
}
int d = h[x] - h[y];
for(int i = 0; i <30; i ++)
{
if((1<<i) && d)
{
ans = max(ans, maxs[x][i]);
x = parent[x][i];
}
}
for(int i = 29; i >=1; i --)
{
if(parent[x][i] != parent[y][i])
{
ans = max(ans, maxs[x][i]);
ans = max(ans, maxs[y][i]);
x = parent[x][i];
y = parent[y][i];
}
}
ans = max(ans, maxs[x][0]);
ans= max(ans, maxs[y][0]);
return ans;
}
int main()
{
int n, m, q;
cin >> n >> m >> q;
vector<pair<int, int>> queries;
for(int i = 0, a, b; i <q; i ++)
{
cin >> a >> b;
queries.push_back({a, b});
}
construct(n);
for(int i = m; i >=1; i --)
{
for(int f = 2; f* i <=n; f ++)
{
int a =find(i);
int b = find(f * i);
if (a!= b)
{
unite(a, b, m - i + 1);
}
}
}
for(int i = 0; i < q; i ++)
{
int a = queries[i].first;
int b = queries[i].second;
int ans = 0;
while(a != b )
{
ans = max(ans, par[a].second);
ans = max(ans, par[b].second);
a = par[a].first, b = par[b].first;
}
cout << ans << '\n';
}
/*
for(int i = 1; i <=n; i ++)
{
for(auto v: graph[i])
{
cout<< i << " " << v.first << " " << v.second << '\n';
}
}*/
/*
int root = find(1);
maxs[root][0] = 0;
dfs(root);
for(int k = 1; (1 << k) <=n; k ++)
{
for(int i = 1; i <=n; i ++)
{
maxs[i][k] = max(maxs[i][k-1], maxs[parent[i][k-1]][k-1]);
parent[i][k] = parent[parent[i][k-1]][k-1];
}
}
for(int i = 0; i < queries.size() - 1; i ++)
{
pair<int ,int> q= queries[i];
cout << findmin(q.first, q.second) << '\n';
}
cout << findmin(queries[q-1].first, queries[q-1].second);
*/
}
Compilation message
pictionary.cpp: In function 'int findmin(int, int)':
pictionary.cpp:70:14: warning: '<<' in boolean context, did you mean '<'? [-Wint-in-bool-context]
70 | if((1<<i) && d)
| ~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
6040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
6608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
6568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
7124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
8144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
9168 KB |
Output is correct |
| 2 |
Incorrect |
50 ms |
9672 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
10432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
11784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
