#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int mx=100010;
struct dsu
{
int pa[mx];
inline void init(int n)
{
fill(pa,pa+n+1,0);
return;
}
int par(int x)
{
if(pa[x]==0)
return x;
return pa[x]=par(pa[x]);
}
inline void uni(int x,int y)
{
x=par(x);
y=par(y);
if(x==y)
return;
pa[x]=y;
return;
}
}uf;
struct seg
{
int t[mx*4];
void init(int n,int s,int e)
{
t[n]=e-s+1;
if(s==e)
return;
int m=s+(e-s)/2;
init(n*2,s,m);
init(n*2+1,m+1,e);
return;
}
inline void put(int n)
{
t[n]=0;
return;
}
inline void prop(int n)
{
if(t[n]!=0)
return;
put(n*2),put(n*2+1);
return;
}
void upd(int n,int s,int e,int S,int E)
{
if(s>E||S>e)
return;
if(S<=s&&e<=E)
return put(n);
prop(n);
int m=s+(e-s)/2;
upd(n*2,s,m,S,E);
upd(n*2+1,m+1,e,S,E);
return;
}
int query(int n,int s,int e,int S,int E)
{
if(s>E||S>e)
return 0;
if(S<=s&&e<=E)
return t[n];
prop(n);
int m=s+(e-s)/2;
return query(n*2,s,m,S,E)+query(n*2+1,m+1,e,S,E);
}
}st;
int dep[mx];
int spa[mx][17];
inline int kpa(int x,int k)
{
for(;k>0;k^=k&-k)
x=spa[x][__builtin_ctz(k)];
return x;
}
inline int lca(int x,int y)
{
if(dep[x]>dep[y])
x=kpa(x,dep[x]-dep[y]);
else
y=kpa(y,dep[y]-dep[x]);
if(x==y)
return x;
for(int i=17;i-->0;)
if(spa[x][i]!=spa[y][i])
x=spa[x][i],y=spa[y][i];
return spa[x][0];
}
vector<int>adj[mx];
int sz[mx];
void dfs(int x)
{
for(int i=0;i<16;i++)
spa[x][i+1]=spa[spa[x][i]][i];
sz[x]=1;
for(int&t:adj[x])
dep[t]=dep[spa[t][0]=x]+1,adj[t].erase(find(all(adj[t]),x)),dfs(t),sz[x]+=sz[t];
sort(all(adj[x]),[&](const int&x,const int&y){return sz[x]>sz[y];});
return;
}
int ord[mx];
int ocnt;
int hc[mx];
void hld(int x)
{
if(hc[x]==0)
hc[x]=x;
ord[x]=++ocnt;
if(!adj[x].empty())
hc[adj[x][0]]=hc[x];
for(int&t:adj[x])
hld(t);
return;
}
inline void upd(int u,int v)
{
while(hc[u]!=hc[v])
{
if(dep[u]<dep[v])
swap(u,v);
st.upd(1,1,sz[1],ord[hc[u]],ord[u]);
u=spa[hc[u]][0];
}
if(dep[u]<dep[v])
swap(u,v);
st.upd(1,1,sz[1],ord[v]+1,ord[u]);
return;
}
inline int query(int u,int v)
{
int sm=0;
while(hc[u]!=hc[v])
{
if(dep[u]<dep[v])
swap(u,v);
sm+=st.query(1,1,sz[1],ord[hc[u]],ord[u]);
u=spa[hc[u]][0];
}
if(dep[u]<dep[v])
swap(u,v);
sm+=st.query(1,1,sz[1],ord[v]+1,ord[u]);
return sm;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<pair<int,pi> >qv;
vector<pi>ted;
for(int i=0;i<m;i++)
{
int t,u,v;
cin>>t>>u>>v;
qv.eb(t,pi(u,v));
if(t==1)
{
if(uf.par(u)!=uf.par(v))
uf.uni(u,v),ted.eb(u,v);
}
}
for(pi&t:ted)
adj[t.fi].eb(t.se),adj[t.se].eb(t.fi);
for(int i=0;i++<n;)
if(hc[i]==0)
dfs(i),hld(i);
st.init(1,1,n);
uf.init(n);
for(auto&tq:qv)
{
int t=tq.fi;
int u=tq.se.fi,v=tq.se.se;
if(t==1)
{
if(uf.par(u)!=uf.par(v))
uf.uni(u,v);
else
upd(u,v);
}
else
{
if(uf.par(u)!=uf.par(v))
cout<<"-1\n";
else
cout<<query(u,v)<<'\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2944 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2848 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
346 ms |
20376 KB |
Output is correct |
| 2 |
Incorrect |
648 ms |
20120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
337 ms |
20628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
210 ms |
19096 KB |
Output is correct |
| 2 |
Incorrect |
360 ms |
18720 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2944 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2848 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
