#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int n, m, k;
pair<int, int> queries[maxn];
int answers[maxn];
struct DSU
{
int par[maxn];
int dep[maxn];
void init(int n)
{
for (int i = 1; i <= n; ++i)
{
dep[i] = 1;
par[i] = i;
}
}
int root(int node)
{
if (node == par[node]) return node;
return par[node] = root(par[node]);
}
void connect(int x, int y)
{
x = root(x);
y = root(y);
if (x == y) return;
if (dep[x] < dep[y]) swap(x, y);
par[y] = x;
if (dep[x] == dep[y]) ++dep[x];
}
bool areConnected(int x, int y)
{
return root(x) == root(y);
}
};
DSU dsu;
vector<int> tree[4 * maxn];
struct ParallelNode
{
int node;
int l;
int r;
int level;
};
void fastIO()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main()
{
fastIO();
cin >> n >> m >> k;
for (int i = 1; i <= k; ++i)
{
cin >> queries[i].first >> queries[i].second;
}
for (int i = 1; i <= k; ++i)
{
tree[1].push_back(i);
answers[i] = m;
}
int prvLevel = -1;
int ptrLevel = 0;
queue<ParallelNode> q;
q.push({1, 1, m, 1});
while (!q.empty())
{
ParallelNode curr = q.front();
q.pop();
if (prvLevel != curr.level)
{
prvLevel = curr.level;
dsu.init(n);
ptrLevel = 0;
}
int mid = (curr.l + curr.r) / 2;
for (int i = ptrLevel + 1; i <= mid; ++i)
{
int gcd = m - i + 1;
for (int i = gcd; i + gcd <= n; i += gcd)
{
dsu.connect(i, i + gcd);
}
}
ptrLevel = mid;
int node = curr.node;
for (int i = 0; i < tree[node].size(); ++i)
{
int idx = tree[node][i];
//cout << mid << " :: " << queries[idx].first << " " << queries[idx].second << " :: " << dsu.areConnected(queries[idx].first, queries[idx].second) << endl;
if (dsu.areConnected(queries[idx].first, queries[idx].second) == true)
{
answers[idx] = min(answers[idx], mid);
tree[2 * node].push_back(idx);
}
else
{
tree[2 * node + 1].push_back(idx);
}
}
if (curr.l == curr.r) continue;
if (!tree[2 * node].empty())
{
q.push({2 * node, curr.l, mid, curr.level + 1});
}
if (!tree[2 * node + 1].empty())
{
q.push({2 * node + 1, mid + 1, curr.r, curr.level + 1});
}
}
for (int i = 1; i <= k; ++i)
{
cout << answers[i] << "\n";
}
return 0;
}
Compilation message
pictionary.cpp: In function 'int main()':
pictionary.cpp:119:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for (int i = 0; i < tree[node].size(); ++i)
| ~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
10072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
11100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
14820 KB |
Output is correct |
| 2 |
Correct |
21 ms |
14044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
17068 KB |
Output is correct |
| 2 |
Correct |
29 ms |
15876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
15608 KB |
Output is correct |
| 2 |
Correct |
36 ms |
14932 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
16476 KB |
Output is correct |
| 2 |
Correct |
36 ms |
14636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
19076 KB |
Output is correct |
| 2 |
Correct |
46 ms |
16204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
16636 KB |
Output is correct |
| 2 |
Correct |
76 ms |
21052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
23180 KB |
Output is correct |
| 2 |
Correct |
76 ms |
21192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
94 ms |
48536 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
