#include<bits/stdc++.h>
using namespace std;
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][20];
int parent[100005][20];
bool visited[100005];
int h[100005];
void construct(int n)
{
for(int i = 0; i <=n; i ++)
{
par[i] = i;
sz[i] = 1;
}
}
int find(int a)
{
if(par[a] !=a)
{
par[a] = find(par[a]);
return par[a];
}
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;
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 <20; i ++)
{
if((1<<i) && d)
{
ans = max(ans, maxs[x][i]);
x = parent[x][i];
}
}
for(int i = 19; 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 = 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:71:14: warning: '<<' in boolean context, did you mean '<'? [-Wint-in-bool-context]
71 | if((1<<i) && d)
| ~~^~~~
pictionary.cpp: In function 'int main()':
pictionary.cpp:139:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for(int i = 0; i < queries.size() - 1; i ++)
| ~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
3340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
4300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
5060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
8396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
10440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
14064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
17600 KB |
Output is correct |
| 2 |
Incorrect |
71 ms |
19396 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
21408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
26304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
