#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];
// assert(ps == pe);
chk[ps] = 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);
// assert(fs == fe);
return chk[fs];
}
};
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];
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];
assert(dep[x] > dep[lca]);
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];
assert(dep[y] > dep[lca]);
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];
assert(dep[x] > dep[lca]);
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];
assert(dep[y] > dep[lca]);
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
852 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
1492 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
223 ms |
53688 KB |
Output is correct |
| 2 |
Runtime error |
165 ms |
108116 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
201 ms |
53764 KB |
Output is correct |
| 2 |
Runtime error |
161 ms |
108072 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
148 ms |
48060 KB |
Output is correct |
| 2 |
Runtime error |
128 ms |
96928 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
852 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
1492 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
