#include <bits/stdc++.h>
using namespace std;
#define int long long
vector <vector <pair <int, int> > > g;
vector <int> dsu, rang;
int get(int a)
{
if(a == dsu[a]) return a;
else return dsu[a] = get(dsu[a]);
}
void unite(int a, int b)
{
a = get(a);
b = get(b);
if(rang[a] < rang[b])
{
swap(a, b);
}
dsu[b] = a;
if(rang[a] == rang[b])
{
rang[a]++;
}
}
vector <vector <int> > rmqpr, rmqw;
vector <int> tin, tout;
int timer = 0;
void dfs(int v, int p = -1)
{
tin[v] = timer++;
for(int i = 0; i < g[v].size(); i++)
{
int to = g[v][i].first;
int w = g[v][i].second;
if(to != p)
{
rmqpr[0][to] = v;
rmqw[0][to] = w;
dfs(to, v);
}
}
tout[v] = timer++;
}
bool pred(int a, int b)
{
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lcaweight(int a, int b)
{
if(a == b)
{
return 0;
}
int ans = 0;
for(int j = rmqpr.size() - 1; j >= 0; j--)
{
if(!pred(rmqpr[j][a], b))
{
ans = max(ans, rmqw[j][a]);
a = rmqpr[j][a];
}
}
for(int j = rmqpr.size() - 1; j >= 0; j--)
{
if(!pred(rmqpr[j][b], a))
{
ans = max(ans, rmqw[j][b]);
b = rmqpr[j][b];
}
}
if(!pred(a, b))
{
ans = max(ans, rmqw[0][a]);
}
if(!pred(b, a))
{
ans = max(ans, rmqw[0][b]);
}
return ans;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m, q;
cin >> n >> m >> q;
g.resize(n);
tin.resize(n);
tout.resize(n);
dsu.resize(n + 1);
rang.resize(n + 1);
for(int i = 1; i <= n; i++)
{
dsu[i] = i;
rang[i] = 1;
}
for(int i = m; i >= 1; i--)
{
int j = i;
while(j + i <= n)
{
if(get(j) != get(j + i))
{
unite(j, j + i);
g[j - 1].push_back({j + i - 1, m - i + 1});
g[j + i - 1].push_back({j - 1, m - i + 1});
}
j += i;
}
}
int t = log2(n) + 1;
rmqpr.resize(t, vector <int> (n, 0));
rmqw.resize(t, vector <int> (n, 0));
dfs(0);
for(int i = 1; i < t; i++)
{
for(int j = 0; j < n; j++)
{
rmqpr[i][j] = rmqpr[i - 1][rmqpr[i - 1][j]];
rmqw[i][j] = max(rmqw[i - 1][j], rmqw[i - 1][rmqpr[i - 1][j]]);
}
}
while(q--)
{
int a, b;
cin >> a >> b;
a--;
b--;
cout << lcaweight(a, b) << "\n";
}
return 0;
}
Compilation message
pictionary.cpp: In function 'void dfs(long long int, long long int)':
pictionary.cpp:31:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
1408 KB |
Output is correct |
| 2 |
Correct |
32 ms |
1400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
1912 KB |
Output is correct |
| 2 |
Correct |
38 ms |
1760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
9032 KB |
Output is correct |
| 2 |
Correct |
42 ms |
8912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
12288 KB |
Output is correct |
| 2 |
Correct |
75 ms |
14264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
18296 KB |
Output is correct |
| 2 |
Correct |
81 ms |
19064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
132 ms |
24340 KB |
Output is correct |
| 2 |
Correct |
147 ms |
28236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
164 ms |
31604 KB |
Output is correct |
| 2 |
Correct |
182 ms |
35872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
218 ms |
40540 KB |
Output is correct |
| 2 |
Correct |
204 ms |
40348 KB |
Output is correct |
