求代码,我这里如果写上路径压缩是 40 分
by 王熙文 @ 2022-12-25 15:57:08
应该可以两个两个地压缩吧(
by Eznibuil @ 2022-12-25 16:01:18
@[王熙文](/user/353688)
```cpp
#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
using namespace std;
const int INF=5e5+5;
struct _node_data{
int a1,a2,a3,a4;
};
_node_data s[INF];
int r;
int n,m,k,fa_set[INF],sz[INF],ans[INF],sum;
int find_set(int x) {return x==fa_set[x]?x:fa_set[x]=find_set(fa_set[x]);}
void mer(int x,int y) {
x=find_set(x);y=find_set(y);
if (x==y) return ;
if (sz[x]>sz[y]) swap(x,y);
s[++r]={x,y,sz[y],sz[x]};
fa_set[x]=y;
sz[y]=max(sz[y],sz[x]+1);
sz[x]=0;
return ;
}
void del() {
int x=s[r].a1,y=s[r].a2;
fa_set[x]=x;
sz[y]=s[r].a3;
sz[x]=s[r].a4;
r--;
}
struct Segment{
#define ll tl[id]
#define rr tr[id]
#define ls(x) x<<1
#define rs(x) x<<1|1
vector < pii > vv[INF<<2];
int tl[INF<<2],tr[INF<<2];
void build(int l,int r,int id) {
ll=l;rr=r;
if (l==r) return ;
int Mid=(ll+rr)>>1;
build(l,Mid,ls(id));
build(Mid+1,r,rs(id));
}
void add(int l,int r,int x,int y,int id) {
if (l<=ll && rr<=r) {vv[id].pb({x,y});return ;}
int Mid=(ll+rr)>>1;
if (l<=Mid) add(l,r,x,y,ls(id));
if (Mid<r) add(l,r,x,y,rs(id));
return ;
}
void solve(int x,int id) {
int kk=r,fl=0;
for (pii i:vv[id]) {
if (find_set(i.fi)==find_set(i.se)) {
for (int j=ll;j<=rr;j++) ans[j]=0;
fl=1;
break;
}
mer(i.fi+n,i.se);
mer(i.fi,i.se+n);
}
if (fl) {while (kk!=r) del();return ;}
if (ll==rr) {
ans[ll]=x;
while (kk!=r) del();
return ;
}
solve(x,ls(id));solve(x,rs(id));
while (kk!=r) del();
}
#undef ll
#undef rr
}T1;
signed main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>k;
for (int i=1;i<=n*2;i++) fa_set[i]=i,sz[i]=1;
T1.build(1,k,1);
for (int i=1;i<=m;i++) {
int x=0,y=0,l=0,r=0;
cin>>x>>y>>l>>r;
if (l==r) continue;
T1.add(l+1,r,x,y,1);
}
T1.solve(1,1);
for (int i=1;i<=k;i++)
cout<<(ans[i]?"Yes":"No")<<"\n";
return 0;
}
```
by 方123456 @ 2022-12-25 16:02:54