#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(all(x))
#define press(x) x.erase(unique(all(x)), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
const int INF=1e9;
const LL LLINF=1e18;
struct UNION_FIND{
int par[100010];
void init(){for(int i=1; i<=100000; i++)par[i]=i;}
int findpar(int num){return num==par[num]?num:par[num]=findpar(par[num]);}
void mergepar(int a, int b){par[findpar(a)]=findpar(b);}
}uf;
vector<int> link[100010];
int p[100010], sz[100010], eul[100010], re, d[100010];
int col[100010], tp[100010], c;
bool ch[100010];
void dfs1(int num, int par){
ch[num]=true;
sz[num]=1;
d[num]=d[par]+1;
p[num]=par;
for(auto i:link[num]){
if(i==par)continue;
dfs1(i, num);
sz[num]+=sz[i];
}
}
bool cmp(int a, int b){return sz[a]>sz[b];}
void dfs2(int num, int par, int cl){
ch[num]=true;
col[num]=cl;
eul[num]=++re;
bool flg=false;
sort(all(link[num]), cmp);
for(auto i:link[num]){
if(i==par)continue;
if(flg){
tp[++c]=i;
dfs2(i, num, c);
}
else dfs2(i, num, cl);
flg=true;
}
}
struct LAZY_SEG{
pii tree[400010];
int lzy[400010];
void prop(int point, int s, int e){
if(s==e){
tree[point].F+=lzy[point];
lzy[point]=0;
return;
}
lzy[point*2]+=lzy[point];
lzy[point*2+1]+=lzy[point];
lzy[point]=0;
}
void eat(int point, int s, int e){
pii l=tree[point*2], r=tree[point*2+1];
l.F+=lzy[point*2], r.F+=lzy[point*2+1];
tree[point]=mp(min(l.F, r.F), 0);
if(tree[point].F==l.F)tree[point].S+=l.S;
if(tree[point].F==r.F)tree[point].S+=r.S;
}
void init(int point, int s, int e){
tree[point]=mp(0, 1);
if(s==e)return;
init(point*2, s, (s+e)/2);
init(point*2+1, (s+e)/2+1, e);
}
void alter(int point, int s, int e, int a, int b){
if(e<a||s>b)return;
if(a<=s&&e<=b){
lzy[point]++;
return;
}
prop(point, s, e);
alter(point*2, s, (s+e)/2, a, b);
alter(point*2+1, (s+e)/2+1, e, a, b);
eat(point, s, e);
}
pii query(int point, int s, int e, int a, int b){
if(e<a||s>b)return mp(INF, 0);
if(a<=s&&e<=b)return mp(tree[point].F+lzy[point], tree[point].S);
prop(point, s, e);
pii l=query(point*2, s, (s+e)/2, a, b);
pii r=query(point*2+1, (s+e)/2+1, e, a, b);
pii ret=mp(min(l.F, r.F), 0);
if(ret.F==l.F)ret.S+=l.S;
if(ret.F==r.F)ret.S+=r.S;
return ret;
}
}seg;
int lca(int a, int b){
if(col[a]==col[b]){
if(eul[a]<eul[b])return a;
return b;
}
if(col[a]>col[b])swap(a, b);
return lca(a, p[tp[col[b]]]);
}
int n, q;
pair<int, pii> qu[300010];
void update(int a, int b){
int l=lca(a, b);
while(1){
if(col[a]==col[l]){
if(l!=a)seg.alter(1, 1, n, eul[l]+1, eul[a]);
break;
}
seg.alter(1, 1, n, eul[tp[col[a]]], eul[a]);
a=p[tp[col[a]]];
}
while(1){
if(col[b]==col[l]){
if(l!=b)seg.alter(1, 1, n, eul[l]+1, eul[b]);
break;
}
seg.alter(1, 1, n, eul[tp[col[b]]], eul[b]);
b=p[tp[col[b]]];
}
}
int query(int a, int b){
int l=lca(a, b), ret=0;
pii tmp;
while(1){
if(col[a]==col[l]){
if(l!=a){
tmp=seg.query(1, 1, n, eul[l]+1, eul[a]);
if(tmp.F==0)ret+=tmp.S;
}
break;
}
tmp=seg.query(1, 1, n, eul[tp[col[a]]], eul[a]);
if(tmp.F==0)ret+=tmp.S;
a=p[tp[col[a]]];
}
while(1){
if(col[b]==col[l]){
if(l!=b){
tmp=seg.query(1, 1, n, eul[l]+1, eul[b]);
if(tmp.F==0)ret+=tmp.S;
}
break;
}
tmp=seg.query(1, 1, n, eul[tp[col[b]]], eul[b]);
if(tmp.F==0)ret+=tmp.S;
b=p[tp[col[b]]];
}
return ret;
}
int main(){
scanf("%d %d", &n, &q);
uf.init();
seg.init(1, 1, n);
for(int i=1; i<=q; i++){
scanf("%d %d %d", &qu[i].F, &qu[i].S.F, &qu[i].S.S);
if(qu[i].F==2)continue;
if(uf.findpar(qu[i].S.F)!=uf.findpar(qu[i].S.S)){
uf.mergepar(qu[i].S.F, qu[i].S.S);
link[qu[i].S.F].eb(qu[i].S.S);
link[qu[i].S.S].eb(qu[i].S.F);
}
}
for(int i=1; i<=n; i++){
if(ch[i])continue;
dfs1(i, 0);
}
memset(ch, 0, sizeof ch);
for(int i=1; i<=n; i++){
if(ch[i])continue;
tp[++c]=i;
dfs2(i, 0, c);
}
uf.init();
for(int i=1; i<=q; i++){
if(qu[i].F==1){
if(uf.findpar(qu[i].S.F)!=uf.findpar(qu[i].S.S))
uf.mergepar(qu[i].S.F, qu[i].S.S);
else update(qu[i].S.F, qu[i].S.S);
}
else{
if(uf.findpar(qu[i].S.F)!=uf.findpar(qu[i].S.S))puts("-1");
else printf("%d\n", query(qu[i].S.F, qu[i].S.S));
}
}
}
Compilation message
road_development.cpp: In function 'int main()':
road_development.cpp:173:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
173 | scanf("%d %d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~
road_development.cpp:177:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
177 | scanf("%d %d %d", &qu[i].F, &qu[i].S.F, &qu[i].S.S);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
6400 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
6400 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
353 ms |
17288 KB |
Output is correct |
| 2 |
Incorrect |
814 ms |
20600 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
383 ms |
17392 KB |
Output is correct |
| 2 |
Incorrect |
631 ms |
20728 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
251 ms |
15984 KB |
Output is correct |
| 2 |
Incorrect |
514 ms |
15480 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
6400 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
6400 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
