Submission #1411389

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <cmath>
#include <string>
#define SIZE 200005
#define INF 1000000000

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

struct MaxFlow
{
	struct edge
	{
		int to,cap,rev;
		edge(int to=0,int cap=0,int rev=0):to(to),cap(cap),rev(rev){}
	};
	vector <edge> vec[SIZE];
	int level[SIZE];
	int iter[SIZE];
	int N;
	
	void init(int X)
	{
		N=X;
	}
	void add(int s,int t,int c)
	{
		int S=vec[s].size(),T=vec[t].size();
		vec[s].push_back(edge(t,c,T));
		vec[t].push_back(edge(s,0,S));
	}
	void bfs(int s)
	{
		memset(level,-1,sizeof(level));
		queue <int> que;
		level[s] = 0;
		que.push(s);
		while (!que.empty())
		{
			int v = que.front();que.pop();
			for(int i=0;i<vec[v].size();i++)
			{
				edge&e=vec[v][i];
				if (e.cap>0&&level[e.to]<0)
				{
					level[e.to]=level[v]+1;
					que.push(e.to);
				}
			}
		}
	}
	int flow_dfs(int v,int t,int f)
	{
		if (v==t) return f;
		for(int &i=iter[v];i<vec[v].size();i++)
		{
			edge &e=vec[v][i];
			if (e.cap>0&&level[v]<level[e.to])
			{
				int d=flow_dfs(e.to,t,min(f,e.cap));
				if(d>0)
				{
					e.cap-=d;
					vec[e.to][e.rev].cap+=d;
					return d;
				}
			}
		}
		return 0;
	}
	int max_flow(int s,int t)
	{
		int flow = 0;
		while(1)
		{
			bfs(s);
			if (level[t]<0) return flow;
			for(int i=0;i<N;i++) iter[i]=0;
			while (1)
			{
				int f=flow_dfs(s,t,INF);
				if(f==0) break;
				flow += f;
			}
		}
	}
};
MaxFlow MT;
struct UF
{
	int par[SIZE],rank[SIZE];
	
	void init(int n)
	{
		for(int i=0;i<n;i++)
		{
			par[i]=i;
			rank[i]=1;
		}
	}
	int find(int x)
	{
		if(x==par[x]) return x;
		return par[x]=find(par[x]);
	}
	void unite(int x,int y)
	{
		x=find(x);
		y=find(y);
		if(x==y) return;
		if(rank[x]<rank[y])
		{
			par[x]=y;
		}
		else
		{
			par[y]=x;
			if(rank[x]==rank[y]) rank[x]++;
		}
	}
	bool same(int x,int y)
	{
		return find(x)==find(y);
	}
};
UF uf;
vector <int> vec[SIZE];
int A[SIZE],B[SIZE],C[SIZE],D[SIZE];
int out[SIZE],in[SIZE];

int main()
{
	int n,H;
	scanf("%d %d",&n,&H);
	for(int i=0;i<n;i++)
	{
		scanf("%d %d %d %d",&A[i],&B[i],&C[i],&D[i]);
		if(C[i]==0) C[i]=1;
		else
		{
			A[i]=C[i];
			C[i]=0;
		}
		if(D[i]==0) D[i]=0;
		else
		{
			B[i]=D[i];
			D[i]=1;
		}
	}
	vector <P> vx;
	for(int i=0;i<n;i++)
	{
		vx.push_back(P(A[i],C[i]));
		vx.push_back(P(B[i],D[i]));
	}
	sort(vx.begin(),vx.end());
	vx.erase(unique(vx.begin(),vx.end()),vx.end());
	uf.init(vx.size()+2);
	for(int i=0;i<n;i++)
	{
		int L=lower_bound(vx.begin(),vx.end(),P(A[i],C[i]))-vx.begin();
		int R=lower_bound(vx.begin(),vx.end(),P(B[i],D[i]))-vx.begin();
		out[L]++,in[R]++;
		uf.unite(L,R);
	}
	for(int i=0;i<vx.size();i++)
	{
		if(uf.find(i)==i)
		{
			vector <int> nd;
			for(int j=0;j<vx.size();j++)
			{
				if(uf.same(i,j))
				{
					nd.push_back(j);
				}
			}
			int a=0,b=0;
			for(int j=0;j<nd.size();j++)
			{
				int v=nd[j];
				if(in[v]==out[v]) continue;
				if(in[v]<out[v])
				{
					if(vx[v].second==0)
					{
						puts("NO");
						return 0;
					}
					a+=out[v]-in[v];
				}
				else
				{
					if(vx[v].second==1)
					{
						puts("NO");
						return 0;
					}
					b+=in[v]-out[v];
				}
			}
			if(a!=b||a==0)
			{
				puts("NO");
				return 0;
			}
		}
	}
	MT.init(vx.size()+5);
	int S=vx.size(),T=S+1;
	int cnt=0;
	for(int i=0;i<vx.size();i++)
	{
		if(in[i]<out[i])
		{
			MT.add(S,i,out[i]-in[i]);
			cnt+=out[i]-in[i];
		}
		else if(out[i]<in[i])
		{
			MT.add(i,T,in[i]-out[i]);
		}
	}
	for(int i=0;i<n;i++)
	{
		int L=lower_bound(vx.begin(),vx.end(),P(A[i],C[i]))-vx.begin();
		int R=lower_bound(vx.begin(),vx.end(),P(B[i],D[i]))-vx.begin();
		MT.add(L,R,1);
	}
	bool up=MT.max_flow(S,T)==cnt;
	if(up) puts("YES");
	else puts("NO");
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:143:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&H);
                      ^
./Main.cpp:146:47: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d",&A[i],&B[i],&C[i],&D[i]);
                                               ^

Judge Result