bzoj 4025: 二分图

Description

神犇有一个n个节点的图。因为神犇是神犇，所以在T时间内一些边会出现后消失。神犇要求出每一时间段内这个图是否是二分图。这么简单的问题神犇当然会做了，于是他想考考你。

解题报告：

用时：2h30min，4WA

这题比较吼，首先想到要找奇环，然后我就不加思考的直接找奇环，然后取环上时间的公共部分，差分一波，发现时间不允许，然后线段树乱优化，发现并不能够维护，然后这么挂了，最后听说是cdq，按时间作为区间分治，然后加上完全在区间内的所有边，判断奇环，这里用到并查集的按秩合并，不能路径压缩，每一次把秩小的合并到大的，手玩发现复杂度是可以的，每一次暴力改回即可

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <vector>

#include <cstdio>

#include <cmath>

#define RG register

#define il inline

#define iter iterator

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;

const int N=100005;

int fa[N],d[N],n,m,T,ans[N],dis[N];

struct node{int x,y,l,r;};

vector<node>S;

int find(int x){while(x!=fa[x])x=fa[x];return x;}

int getdis(int x){

   int ret=0;

   while(x!=fa[x])ret^=dis[x],x=fa[x];

   return ret;

}

int st[N<<2],top=0;

void merge(int x,int y,int to){

   if(d[x]>d[y])swap(x,y);

   if(d[x]==d[y])d[y]++,st[++top]=-y;

   st[++top]=x;fa[x]=y;dis[x]=to;

}

void Clear(int last){

   while(top!=last){

      if(st[top]<0)d[-st[top]]--;

      else fa[st[top]]=st[top],dis[st[top]]=0;

      top--;

   }

}

void solve(int l,int r,vector<node>S){

   node a;int to,x,y,fx,fy,mid=(l+r)>>1,sz=S.size(),last=top;

   vector<node>ll,rr;

   for(int i=0;i<sz;i++){

      a=S[i];

      if(a.l==l && a.r==r){

         x=a.x;y=a.y;

         fx=find(x);fy=find(y);

         to=getdis(x)^getdis(y)^1;

         if(fx!=fy)merge(fx,fy,to);

         else{

            if(to==1){

               for(int j=l;j<=r;j++)ans[j]=1;

               Clear(last);return ;

            }

         }

      }

      else if(a.r<=mid)ll.push_back(a);

      else if(a.l>mid)rr.push_back(a);

      else{

         ll.push_back((node){a.x,a.y,a.l,mid});

         rr.push_back((node){a.x,a.y,mid+1,a.r});

      }

   }

   if(l!=r)solve(l,mid,ll),solve(mid+1,r,rr);

   Clear(last);

}

void work()

{

   int x,y,s,t;

   scanf("%d%d%d",&n,&m,&T);

   for(int i=1;i<=n;i++)fa[i]=i,d[i]=0;

   for(int i=1;i<=m;i++){

      scanf("%d%d%d%d",&x,&y,&s,&t);

      if(s<t)S.push_back((node){x,y,s+1,t});

   }

   solve(1,T,S);

   for(int i=1;i<=T;i++)ans[i]?puts("No"):puts("Yes");

}

int main()

{

	work();

	return 0;

}

错的乱搞:

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#define RG register

#define il inline

#define ls (node<<1)

#define rs (node<<1|1)

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;

const int N=100005,M=200005;

int head[N],num=0,nxt[M<<1],to[M<<1],s[M<<1],t[M<<1],n,m,T,dfn[N],vis[N];

void link(int x,int y,int St,int Tt){

   nxt[++num]=head[x];to[num]=y;head[x]=num;

   s[num]=St;t[num]=Tt;

}

struct seg{int min,max;}tr[N<<2];int ans[N];bool app[N];

void upd(int node){

   tr[node].min=Min(tr[ls].min,tr[rs].min);

   tr[node].max=Max(tr[ls].max,tr[rs].max);

}

void updata(int l,int r,int node,int sa,int id){

   if(l>sa || r<sa)return ;

   if(l==r){tr[node].min=t[id];tr[node].max=s[id];return ;}

   int mid=(l+r)>>1;

   updata(l,mid,ls,sa,id);updata(mid+1,r,rs,sa,id);

   upd(node);

}

seg query(int l,int r,int node,int sa,int se){

   if(sa<=l && r<=se)return tr[node];

   int mid=(l+r)>>1;

   if(se<=mid)return query(l,mid,ls,sa,se);

   else if(sa>mid)return query(mid+1,r,rs,sa,se);

   else{

      seg q1,q2,ret;

      q1=query(l,mid,ls,sa,se);q2=query(mid+1,r,rs,sa,se);

      ret.min=Min(q1.min,q2.min);ret.max=Max(q1.max,q2.max);

      return ret;

   }

}

void solve(int x,int y,int i){

   seg tmp=query(1,n,1,dfn[x],dfn[y]-1);

   tmp.min=Min(tmp.min,t[i]);

   tmp.max=Max(tmp.max,s[i]);

   if(tmp.min>=tmp.max)

      ans[tmp.max+1]--,ans[tmp.min]++;

}

void dfs(int x,int last,int dep){

   int u;dfn[x]=dep;

   for(int i=head[x];i;i=nxt[i]){

      u=to[i];if(u==last || app[i])continue;

      if(vis[u]==vis[x]){

         solve(u,x,i);

         app[i]=app[i^1]=true;

         continue;

      }

      updata(1,n,1,dep,i);

      if(!vis[u])vis[u]=3-vis[x],dfs(u,x,dep+1);

   }

}

void work()

{

   int x,y,St,Tt;

   scanf("%d%d%d",&n,&m,&T);

   for(int i=1;i<=m;i++){

      scanf("%d%d%d%d",&x,&y,&St,&Tt);

      link(x,y,St,Tt-1);link(y,x,St,Tt-1);

   }

   vis[1]=1;dfs(1,1,1);

   for(int i=1;i<=T;i++)ans[i]+=ans[i-1];

   for(int i=0;i<T;i++)

      if(ans[i])puts("No");

      else puts("Yes");

}

int main()

{

	work();

	return 0;

}

巴特西

bzoj 4025: 二分图

最新文章

热门文章