#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;
struct Dsu{
int n;
vector<int> pr;
Dsu(int N){
n = N + 4;
pr.resize(n);
iota(pr.begin(), pr.end(), 0);
}
int fd(int x){
return (x == pr[x] ? x : pr[x] = fd(pr[x]));
}
bool unite(int x, int y){
x = fd(x), y = fd(y);
if(x != y){
pr[x] = y;
return true;
}
return false;
}
};
struct Seg{
int n;
vector<int> tr, chk;
Seg(int N){
n = N + 4;
tr.resize(n * 4 + 4);
chk.resize(n * 4 + 4);
}
void push(int x, int s, int e, int ps, int pe){
if(pe < s || ps > e) return;
if(ps <= s && pe >= e){
chk[x] = 1;
tr[x] = e - s + 1;
return;
}
int m = s + e >> 1;
push(x * 2, s, m, ps, pe);
push(x * 2 + 1, m + 1, e, ps, pe);
if(chk[x]) tr[x] = e - s + 1;
else tr[x] = tr[x * 2] + tr[x * 2 + 1];
}
int get(int x, int s, int e, int fs, int fe){
if(fe < s || fs > e || fs > fe) return 0;
if(chk[x]) return min(fe, e) - max(fs, s) + 1;
if(fs <= s && fe >= e) return tr[x];
int m = s + e >> 1;
return get(x * 2, s, m, fs, fe) + get(x * 2 + 1, m + 1, e, fs, fe);
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<vector<int>> que(q, vector<int>(3));
vector<vector<int>> way(n);
Dsu gr(n + 4);
for(int i = 0; i < q; ++i){
cin >> que[i][0] >> que[i][1] >> que[i][2];
--que[i][1], --que[i][2];
if(que[i][0] == 1){
if(gr.unite(que[i][1], que[i][2])){
// cout << que[i][1] << ' ' << que[i][2] << endl;
way[que[i][1]].push_back(que[i][2]);
way[que[i][2]].push_back(que[i][1]);
}
}
}
vector<int> dep(n), sz(n), up(n), in(n);
vector<vector<int>> spa(n, vector<int>(20));
int inN = 0;
auto dfs = [&](auto&&self, int x)->void{
for(auto&nxt:way[x]){
if(nxt == spa[x][0]) continue;
spa[nxt][0] = x;
dep[nxt] = dep[x] + 1;
self(self, nxt);
sz[x] += sz[nxt];
}
sz[x] += 1;
};
for(int i = 0; i < n; ++i){
if(!dep[i]){
dep[i] = 1;
spa[i][0] = i;
dfs(dfs, i);
}
}
auto dfshld = [&](auto&&self, int x)->void{
in[x] = ++inN;
for(int i = 0; i < (int)way[x].size(); ++i){
if(way[x][i] == spa[x][0]){
swap(way[x][i], way[x].back());
way[x].pop_back();
break;
}
}
for(int i = 1; i < (int)way[x].size(); ++i){
if(sz[way[x][i]] > sz[way[x][0]]){
swap(way[x][i], way[x][0]);
}
}
for(int i = 0; i < (int)way[x].size(); ++i){
if(!i) up[way[x][i]] = up[x];
else up[way[x][i]] = way[x][i];
self(self, way[x][i]);
}
};
for(int i = 0; i < n; ++i){
if(i == spa[i][0]){
up[i] = i;
dfshld(dfshld, i);
}
}
vector<int> cnt(n);
gr = Dsu(n);
auto getlca = [&](int x, int y){
if(dep[x] > dep[y]) swap(x, y);
for(int i = 19; i >= 0; --i){
if(dep[y] - (1 << i) >= dep[x]){
y = spa[y][i];
}
}
if(x == y) return x;
for(int i = 19; i >= 0; --i){
if(spa[x][i] != spa[y][i]){
x = spa[x][i];
y = spa[y][i];
}
}
return spa[x][0];
};
Seg tr(n + 4);
for(int i = 0; i < q; ++i){
int x = que[i][1], y = que[i][2];
if(que[i][0] == 1){
if(gr.unite(x, y)){
continue;
}
int lca = getlca(x, y);
while(x != lca){
int u = up[x];
if(dep[u] <= dep[lca]) u = way[lca][0];
tr.push(1, 1, n, in[u], in[x]);
x = spa[u][0];
}
while(y != lca){
int u = up[y];
if(dep[u] <= dep[lca]) u = way[lca][0];
tr.push(1, 1, n, in[u], in[y]);
y = spa[u][0];
}
}
else{
if(gr.fd(x) != gr.fd(y)){
cout << "-1\n";
continue;
}
int lca = getlca(x, y);
int ans = dep[x] + dep[y] - dep[lca] * 2;
while(x != lca){
int u = up[x];
if(dep[u] <= dep[lca]) u = way[lca][0];
ans -= tr.get(1, 1, n, in[u], in[x]);
x = spa[u][0];
}
while(y != lca){
int u = up[y];
if(dep[u] <= dep[lca]) u = way[lca][0];
ans -= tr.get(1, 1, n, in[u], in[y]);
y = spa[u][0];
}
cout << ans << '\n';
}
}
return 0;
}
Compilation message
road_development.cpp: In member function 'void Seg::push(long long int, long long int, long long int, long long int, long long int)':
road_development.cpp:44:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
44 | int m = s + e >> 1;
| ~~^~~
road_development.cpp: In member function 'long long int Seg::get(long long int, long long int, long long int, long long int, long long int)':
road_development.cpp:54:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | int m = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
852 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
852 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
300 ms |
53776 KB |
Output is correct |
| 2 |
Incorrect |
369 ms |
53712 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
279 ms |
53780 KB |
Output is correct |
| 2 |
Incorrect |
348 ms |
53716 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
169 ms |
48048 KB |
Output is correct |
| 2 |
Incorrect |
276 ms |
47900 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
852 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
852 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
