#include <iostream>
#include <cmath>
#include <functional>
#include <vector>
using namespace std;
struct Query
{
int t, a, b;
};
Query qr[300005];
struct UnionFind
{
vector<int> par;
UnionFind(int N)
{
par.resize(N+1);
for (int i = 1; i <= N; i++) par[i] = i;
}
int fin(int v)
{
return v == par[v] ? v : (par[v] = fin(par[v]));
}
void uni(int u, int v)
{
par[fin(u)] = fin(v);
}
bool isuni(int u, int v)
{
return fin(u) == fin(v);
}
};
struct LazySeg
{
vector<int> tree, lazy;
LazySeg(int N)
{
int sz = 1 << ((int)ceil(log2(N+1))+1);
tree.resize(sz); lazy.resize(sz);
}
void propagate(int s, int e, int node)
{
if (lazy[node] == 0) return;
tree[node] = e - s + 1;
if (s != e) {
lazy[2*node] = lazy[2*node+1] = 1;
}
lazy[node] = 0;
}
void upd(int s, int e, int node, int l, int r)
{
propagate(s, e, node);
if (e < l || r < s) return;
if (l <= s && e <= r){
lazy[node] = 1;
propagate(s, e, node);
return;
}
upd(s, (s+e)/2, 2*node, l, r);
upd((s+e)/2+1, e, 2*node+1, l, r);
tree[node] = tree[2*node] + tree[2*node+1];
}
int query(int s, int e, int node, int l, int r)
{
if (e < l || r < s) return 0;
if (l <= s && e <= r) return tree[node];
return query(s, (s+e)/2, 2*node, l, r) + query((s+e)/2+1, e, 2*node+1, l, r);
}
};
vector<int> adj[100005];
vector<int> g[100005];
int in[100005], out[100005], sz[100005], par[100005], dep[100005], nxt[100005];
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int N, Q; cin >> N >> Q;
for (int i = 0; i < Q; i++) {
cin >> qr[i].t >> qr[i].a >> qr[i].b;
}
UnionFind uf(N);
for (int i = 0; i < Q; i++) {
if (qr[i].t == 1) {
if (!uf.isuni(qr[i].a, qr[i].b)) {
adj[qr[i].a].push_back(qr[i].b);
adj[qr[i].b].push_back(qr[i].a);
uf.uni(qr[i].a, qr[i].b);
}
}
}
for (int i = 2; i <= N; i++) {
if (!uf.isuni(1, i)) {
uf.uni(1, i);
adj[1].push_back(i);
adj[i].push_back(1);
}
}
LazySeg seg(N);
function<void(int, int)> dfs_sz = [&](int v, int p)
{
dep[v] = dep[p] + 1;
par[v] = p;
sz[v] = 1;
for (int i:adj[v]) {
if (i != p) {
g[v].push_back(i);
dfs_sz(i, v);
if (sz[g[v][0]] < sz[i]) {
swap(g[v][0], g[v].back());
}
sz[v] += sz[i];
}
}
};
int ord = 0;
function<void(int)> dfs_hld = [&](int v)
{
in[v] = ord++;
for (int i:g[v]) {
nxt[i] = g[v][0] == i ? nxt[v] : i;
dfs_hld(i);
}
out[v] = ord;
};
function<int(int, int)> lca = [&](int u, int v)
{
while (nxt[u] != nxt[v]) {
if (dep[nxt[u]] < dep[nxt[v]]) swap(u, v);
u = par[nxt[u]];
}
return dep[u] < dep[v] ? u : v;
};
function<void(int, int)> upd = [&](int u, int v)
{
int w = lca(u, v);
while (1) {
if (nxt[u] != nxt[w]) {
seg.upd(0, N-1, 1, in[nxt[u]], in[u]);
u = par[nxt[u]];
}
else {
seg.upd(0, N-1, 1, in[w]+1, in[u]);
break;
}
}
while (1) {
if (nxt[v] != nxt[w]) {
seg.upd(0, N-1, 1, in[nxt[v]], in[v]);
v = par[nxt[v]];
}
else {
seg.upd(0, N-1, 1, in[w]+1, in[v]);
break;
}
}
};
function<int(int, int)> query = [&](int u, int v)
{
int ans = 0;
int w = lca(u, v);
while (1) {
if (nxt[u] != nxt[w]) {
ans += seg.query(0, N-1, 1, in[nxt[u]], in[u]);
u = par[nxt[u]];
}
else {
ans += seg.query(0, N-1, 1, in[w]+1, in[u]);
break;
}
}
while (1) {
if (nxt[v] != nxt[w]) {
ans += seg.query(0, N-1, 1, in[nxt[v]], in[v]);
v = par[nxt[v]];
}
else {
ans += seg.query(0, N-1, 1, in[w]+1, in[v]);
break;
}
}
return ans;
};
function<int(int, int)> dis = [&](int u, int v)
{
int w = lca(u, v);
return dep[u] + dep[v] - 2 * dep[w];
};
dfs_sz(1, 0);
dfs_hld(1);
UnionFind uf2(N);
for (int i = 0; i < Q; i++) {
if (qr[i].t == 1) {
if (uf2.isuni(qr[i].a, qr[i].b)) {
upd(qr[i].a, qr[i].b);
}
else {
uf2.uni(qr[i].a, qr[i].b);
}
}
else {
if (uf2.isuni(qr[i].a, qr[i].b)) {
cout << dis(qr[i].a, qr[i].b) - query(qr[i].a, qr[i].b) << '\n';
}
else {
cout << -1 << '\n';
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5204 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
5204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
195 ms |
18364 KB |
Output is correct |
| 2 |
Incorrect |
435 ms |
19156 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
205 ms |
18376 KB |
Output is correct |
| 2 |
Incorrect |
306 ms |
19148 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
17016 KB |
Output is correct |
| 2 |
Incorrect |
292 ms |
17836 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5204 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
5204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
