Submission #36446723

---

Source Code Expand

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int in[3000003],que[3000003];
pair<int,int> a[1000001],b[1000001];
vector<int> edg[3000003];
int main()
{
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	int siz_b=0,nc=m;
	for(int i=1;i<=n;++i)
	{
		int siz_a=0,mini=0x7fffffff,maxi=0;
		for(int j=1;j<=m;++j)
		{
			int x;
			cin>>x;
			if(x>0)
			{
				a[++siz_a]=make_pair(x,j);
				mini=min(mini,x);
				maxi=max(maxi,x);
			}
		}
		if(siz_a)
		{
			b[++siz_b].first=mini;
			b[siz_b].second=maxi;
			sort(a+1,a+siz_a+1);
			for(int j=1;j<=siz_a;++j)
			{
				const int sj=j;
				for(;j<siz_a&&a[j+1].first==a[j].first;++j);
				if(j<siz_a)
				{
					const int t=(++nc);
					for(int k=sj;k<=j;edg[a[k].second].emplace_back(t),++k);
					edg[t].emplace_back(a[j+1].second);
					for(int k=j+1;k<siz_a&&a[k+1].first==a[k].first;edg[t].emplace_back(a[++k].second));
				}
			}
		}
	}
	if(siz_b)
	{
		sort(b+1,b+siz_b+1);
		for(int i=1;i<siz_b;++i)
		{
			if(b[i].second>b[i+1].first)
			{
				cout<<"No";
				return 0;
			}
		}
		for(int i=1;i<=nc;++i)
		{
			for(auto &j:edg[i])
			{
				++in[j];
			}
		}
		int ta=0;
		for(int i=1;i<=nc;++i)if(in[i]==0)que[++ta]=i;
		for(int he=1;he<=ta;)
		{
			const int pos=que[he++];
			for(int j:edg[pos])
			{
				if((--in[j])==0)
				{
					que[++ta]=j;
				}
			}
		}
		if(ta!=nc)
		{
			cout<<"No";
			return 0;
		}
		cout<<"Yes";
	}
	else
	{
		cout<<"Yes";
	}
	return 0;
}

Submission Info

Judge Result