传送门
思路
是二分图的充要条件: 图没有奇环.
考虑按时间分治, 用可撤销并查集维护点到根的距离.
仍然可以用一个小 trick 把两点连边变成根连边, 可以看这里 https://www.cnblogs.com/p-b-p-b/p/10358109.html .
每次连边时若不连通则连上, 否则判一下有没有奇环. 如果有输出 "No", 否则不用连.
我 tm 把 T 写成 m 狂 WA 不止
- #include<bits/stdc++.h>
- namespace my_std{
- using namespace std;
- #define pii pair<int,int>
- #define fir first
- #define sec second
- #define MP make_pair
- #define rep(i,x,y) for (int i=(x);i<=(y);i++)
- #define drep(i,x,y) for (int i=(x);i>=(y);i--)
- #define go(x) for (int i=head[x];i;i=edge[i].nxt)
- #define sz 202020
- typedef long long ll;
- template<typename T>
- inline void read(T& t)
- {
- t=0;char f=0,ch=getchar();
- double d=0.1;
- while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
- while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
- if(ch=='.')
- {
- ch=getchar();
- while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();
- }
- t=(f?-t:t);
- }
- template<typename T,typename... Args>
- inline void read(T& t,Args&... args){read(t); read(args...);}
- void file()
- {
- #ifndef ONLINE_JUDGE
- freopen("a.txt","r",stdin);
- #endif
- }
- // inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
- }
- using namespace my_std;
- int n,m,T;
- struct hh{int f,t;hh(int ff=0,int tt=0){f=ff,t=tt;}}edge[sz];
- int fa[sz],dep[sz],f[sz];
- int getfa(int x){return x==fa[x]?x:getfa(fa[x]);}
- int getdis(int x){return x==fa[x]?0:f[x]^getdis(fa[x]);}
- vector<hh>v[sz<<2];
- #define ls k<<1
- #define rs k<<1|1
- #define lson ls,l,mid
- #define rson rs,mid+1,r
- void insert(int k,int l,int r,int x,int y,hh e)
- {
- if (x>y) return;
- if (x<=l&&r<=y) return (void)v[k].push_back(e);
- int mid=(l+r)>>1;
- if (x<=mid) insert(lson,x,y,e);
- if (y>mid) insert(rson,x,y,e);
- }
- struct hhh{int x,y;bool s;};
- void resume(stack<hhh>S){while (!S.empty()) f[fa[S.top().x]=S.top().x]=0,dep[S.top().y]-=S.top().s,S.pop();}
- void solve(int k,int l,int r)
- {
- stack<hhh>S;
- rep(i,0,(int)v[k].size()-1)
- {
- hh e=v[k][i];int x=e.f,y=e.t;
- int fx=getfa(x),fy=getfa(y);
- int w=getdis(x)^getdis(y)^1;
- if (fx==fy&&w) { rep(i,l,r) puts("No"); resume(S); return; }
- if (fx!=fy)
- {
- if (dep[fx]>dep[fy]) swap(fx,fy),swap(x,y);
- hhh cur=(hhh){fx,fy,0};
- fa[fx]=fy;f[fx]=w;
- if (dep[fx]==dep[fy]) ++dep[fy],cur.s=1;
- S.push(cur);
- }
- }
- if (l==r) return puts("Yes"),resume(S);
- int mid=(l+r)>>1;
- solve(lson);solve(rson);
- resume(S);
- }
- int main()
- {
- file();
- read(n,m,T);
- rep(i,1,n) fa[i]=i;
- int x,y,l,r;
- rep(i,1,m) read(x,y,l,r),edge[i]=hh(x,y),++l,insert(1,1,n,l,r,edge[i]);
- solve(1,1,T); // orz
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2948918.html