#include <bits/stdc++.h>
using namespace std;
void read(int& x){ scanf("%d",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define pb push_back
int n, q;
typedef tuple<int,int,int> tp;
tp qr[300010];
vector<int> edge[100010];
int par[20][100010];
int dep[100010];
struct ASDF {
void init(){
for(int i=1; i<20; ++i) for(int j=1; j<=n; ++j)
par[i][j] = par[i-1][par[i-1][j]];
}
int lca(int a, int b){
if(dep[a] > dep[b]) swap(a, b);
for(int i=19; 0<=i; --i) if(1&((dep[b]-dep[a])>>i)) b=par[i][b];
for(int i=19; 0<=i; --i){
if(par[i][a] != par[i][b]) a=par[i][a], b=par[i][b];
}
if(a^b) a=par[0][a];
return a;
}
} LCA;
struct UFO {
int par[100010];
void init(){ for(int i=1; i<=n; ++i) par[i]=i; }
int root(int x){ return (par[x]==x)?x:(par[x]=root(par[x])); }
void join(int a,int b){
a=root(a); b=root(b);
if(dep[a]>dep[b]) swap(a,b);
par[b]=a;
}
} uf, uf2;
int in[100010];
int out[100010];
int nt;
void dfs(int x){
in[x] = ++nt;
for(int y:edge[x]){
if(par[0][x] == y) continue;
par[0][y] = x;
dep[y] = dep[x]+1;
dfs(y);
}
out[x] = nt;
}
struct SEG {
static const int M = 131072;
int tree[M<<1];
void upd(int l,int r,int val){
l+=M; r+=M;
while(l<=r){
if(l%2==1) tree[l++] += val;
if(r%2==0) tree[r--] += val;
l>>=1; r>>=1;
}
}
int get(int pos){
pos=in[pos];
pos+=M;
int ret=0;
while(pos) ret+=tree[pos], pos>>=1;
return ret;
}
} seg;
void goup(int x,int to){
while(true){
x=uf.root(x);
if(dep[x] <= dep[to]) break;
seg.upd(in[x], out[x], -1);
uf.join(x, par[0][x]);
x=par[0][x];
}
}
int main()
{
read(n, q);
uf.init();
for(int i=1; i<=q; ++i){
int t, a, b;
read(t, a, b);
if(t == 1){
if(uf.root(a) != uf.root(b)){
edge[a].pb(b);
edge[b].pb(a);
uf.join(a, b);
}
}
qr[i] = make_tuple(t, a, b);
}
for(int i=1; i<=n; ++i) if(!in[i]) dfs(i);
for(int i=1; i<=n; ++i) if(par[0][i]) seg.upd(in[i], out[i], 1);
uf.init();
uf2.init();
LCA.init();
//seg.upd(1, nt, 1);
for(int i=1; i<=q; ++i){
int t, a, b; tie(t, a, b) = qr[i];
if(t == 1){
if(uf2.root(a) == uf2.root(b)){
int l=LCA.lca(a, b);
goup(a, l);
goup(b, l);
} else {
uf2.join(a, b);
}
} else {
if(uf2.root(a) != uf2.root(b)){
puts("-1");
} else {
int l=LCA.lca(a, b);
printf("%d\n", seg.get(a) + seg.get(b) - seg.get(l)*2);
}
}
}
return 0;
}
Compilation message
road_development.cpp: In function 'void read(int&)':
road_development.cpp:3:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
3 | void read(int& x){ scanf("%d",&x); }
| ~~~~~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2932 KB |
Output is correct |
2 |
Correct |
4 ms |
2892 KB |
Output is correct |
3 |
Correct |
4 ms |
3020 KB |
Output is correct |
4 |
Correct |
4 ms |
3020 KB |
Output is correct |
5 |
Correct |
4 ms |
2932 KB |
Output is correct |
6 |
Correct |
4 ms |
3020 KB |
Output is correct |
7 |
Correct |
4 ms |
2892 KB |
Output is correct |
8 |
Correct |
4 ms |
3020 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
565 ms |
24104 KB |
Output is correct |
2 |
Correct |
551 ms |
24328 KB |
Output is correct |
3 |
Correct |
598 ms |
28640 KB |
Output is correct |
4 |
Correct |
552 ms |
28796 KB |
Output is correct |
5 |
Correct |
590 ms |
27308 KB |
Output is correct |
6 |
Correct |
680 ms |
27236 KB |
Output is correct |
7 |
Correct |
511 ms |
24248 KB |
Output is correct |
8 |
Correct |
628 ms |
27076 KB |
Output is correct |
9 |
Correct |
557 ms |
23768 KB |
Output is correct |
10 |
Correct |
571 ms |
26188 KB |
Output is correct |
11 |
Correct |
679 ms |
27956 KB |
Output is correct |
12 |
Correct |
566 ms |
30164 KB |
Output is correct |
13 |
Correct |
575 ms |
30492 KB |
Output is correct |
14 |
Correct |
623 ms |
27716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
434 ms |
24192 KB |
Output is correct |
2 |
Correct |
524 ms |
24516 KB |
Output is correct |
3 |
Correct |
651 ms |
27720 KB |
Output is correct |
4 |
Correct |
623 ms |
29292 KB |
Output is correct |
5 |
Correct |
369 ms |
24440 KB |
Output is correct |
6 |
Correct |
634 ms |
27796 KB |
Output is correct |
7 |
Correct |
267 ms |
23996 KB |
Output is correct |
8 |
Correct |
708 ms |
26768 KB |
Output is correct |
9 |
Correct |
483 ms |
27204 KB |
Output is correct |
10 |
Correct |
583 ms |
28412 KB |
Output is correct |
11 |
Correct |
496 ms |
23736 KB |
Output is correct |
12 |
Correct |
589 ms |
28668 KB |
Output is correct |
13 |
Correct |
534 ms |
28844 KB |
Output is correct |
14 |
Correct |
523 ms |
27844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
268 ms |
21316 KB |
Output is correct |
2 |
Correct |
283 ms |
21584 KB |
Output is correct |
3 |
Correct |
349 ms |
24504 KB |
Output is correct |
4 |
Correct |
369 ms |
25892 KB |
Output is correct |
5 |
Correct |
463 ms |
23896 KB |
Output is correct |
6 |
Correct |
564 ms |
28272 KB |
Output is correct |
7 |
Correct |
84 ms |
18960 KB |
Output is correct |
8 |
Correct |
140 ms |
22608 KB |
Output is correct |
9 |
Correct |
138 ms |
24676 KB |
Output is correct |
10 |
Correct |
144 ms |
21376 KB |
Output is correct |
11 |
Correct |
499 ms |
26136 KB |
Output is correct |
12 |
Correct |
492 ms |
26816 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2932 KB |
Output is correct |
2 |
Correct |
4 ms |
2892 KB |
Output is correct |
3 |
Correct |
4 ms |
3020 KB |
Output is correct |
4 |
Correct |
4 ms |
3020 KB |
Output is correct |
5 |
Correct |
4 ms |
2932 KB |
Output is correct |
6 |
Correct |
4 ms |
3020 KB |
Output is correct |
7 |
Correct |
4 ms |
2892 KB |
Output is correct |
8 |
Correct |
4 ms |
3020 KB |
Output is correct |
9 |
Correct |
565 ms |
24104 KB |
Output is correct |
10 |
Correct |
551 ms |
24328 KB |
Output is correct |
11 |
Correct |
598 ms |
28640 KB |
Output is correct |
12 |
Correct |
552 ms |
28796 KB |
Output is correct |
13 |
Correct |
590 ms |
27308 KB |
Output is correct |
14 |
Correct |
680 ms |
27236 KB |
Output is correct |
15 |
Correct |
511 ms |
24248 KB |
Output is correct |
16 |
Correct |
628 ms |
27076 KB |
Output is correct |
17 |
Correct |
557 ms |
23768 KB |
Output is correct |
18 |
Correct |
571 ms |
26188 KB |
Output is correct |
19 |
Correct |
679 ms |
27956 KB |
Output is correct |
20 |
Correct |
566 ms |
30164 KB |
Output is correct |
21 |
Correct |
575 ms |
30492 KB |
Output is correct |
22 |
Correct |
623 ms |
27716 KB |
Output is correct |
23 |
Correct |
434 ms |
24192 KB |
Output is correct |
24 |
Correct |
524 ms |
24516 KB |
Output is correct |
25 |
Correct |
651 ms |
27720 KB |
Output is correct |
26 |
Correct |
623 ms |
29292 KB |
Output is correct |
27 |
Correct |
369 ms |
24440 KB |
Output is correct |
28 |
Correct |
634 ms |
27796 KB |
Output is correct |
29 |
Correct |
267 ms |
23996 KB |
Output is correct |
30 |
Correct |
708 ms |
26768 KB |
Output is correct |
31 |
Correct |
483 ms |
27204 KB |
Output is correct |
32 |
Correct |
583 ms |
28412 KB |
Output is correct |
33 |
Correct |
496 ms |
23736 KB |
Output is correct |
34 |
Correct |
589 ms |
28668 KB |
Output is correct |
35 |
Correct |
534 ms |
28844 KB |
Output is correct |
36 |
Correct |
523 ms |
27844 KB |
Output is correct |
37 |
Correct |
268 ms |
21316 KB |
Output is correct |
38 |
Correct |
283 ms |
21584 KB |
Output is correct |
39 |
Correct |
349 ms |
24504 KB |
Output is correct |
40 |
Correct |
369 ms |
25892 KB |
Output is correct |
41 |
Correct |
463 ms |
23896 KB |
Output is correct |
42 |
Correct |
564 ms |
28272 KB |
Output is correct |
43 |
Correct |
84 ms |
18960 KB |
Output is correct |
44 |
Correct |
140 ms |
22608 KB |
Output is correct |
45 |
Correct |
138 ms |
24676 KB |
Output is correct |
46 |
Correct |
144 ms |
21376 KB |
Output is correct |
47 |
Correct |
499 ms |
26136 KB |
Output is correct |
48 |
Correct |
492 ms |
26816 KB |
Output is correct |
49 |
Correct |
536 ms |
24180 KB |
Output is correct |
50 |
Correct |
423 ms |
24252 KB |
Output is correct |
51 |
Correct |
613 ms |
28456 KB |
Output is correct |
52 |
Correct |
656 ms |
30216 KB |
Output is correct |
53 |
Correct |
380 ms |
23112 KB |
Output is correct |
54 |
Correct |
266 ms |
23464 KB |
Output is correct |
55 |
Correct |
474 ms |
27144 KB |
Output is correct |
56 |
Correct |
567 ms |
28484 KB |
Output is correct |
57 |
Correct |
596 ms |
26916 KB |
Output is correct |
58 |
Correct |
549 ms |
26908 KB |
Output is correct |
59 |
Correct |
472 ms |
27100 KB |
Output is correct |
60 |
Correct |
538 ms |
27716 KB |
Output is correct |
61 |
Correct |
533 ms |
28004 KB |
Output is correct |