Submission #41959796

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN = 2e5+10;

int n,m;
vector<int>e[MAXN];

int L[MAXN],R[MAXN];

int deg[MAXN],topo[MAXN],tot;
queue<int>q;

vector<int>occ[MAXN];

int ret[MAXN],pos[MAXN];
struct Node{
	int u;
	bool operator<(const Node& n2)const{
		return R[u] > R[n2.u];
	}
};	
priority_queue<Node>pq;

int main(){
	ios::sync_with_stdio(false);

	cin>>n>>m;
	rep(i,1,m){
		int u,v;cin>>u>>v;
		e[u].push_back(v);
		deg[v]++;
	}

	rep(i,1,n)cin>>L[i]>>R[i];

	rep(i,1,n)if(!deg[i])q.push(i),topo[++tot]=i;
	while(q.size()){
		int u=q.front();q.pop();
		for(auto v:e[u]){
			deg[v]--;
			if(!deg[v]){
				q.push(v),topo[++tot]=v;
			}
		}
	}
	if(tot < n){
		cout<<"No\n";
		return 0;
	}
	rep(i,1,n){
		int u = topo[i];
		for(auto v:e[u])L[v] = max(L[v],L[u]+1);
	}
	per(i,n,1){
		int u = topo[i];
		for(auto v:e[u])R[u] = min(R[u],R[v]-1);
	}

	rep(i,1,n){
		if(L[i] > R[i]){
			cout<<"No\n";
			return 0;
		}
		occ[L[i]].push_back(i);
	}

	rep(i,1,n){
		for(auto u:occ[i])pq.push((Node){u});
		if(pq.empty()){
			cout<<"No\n";
			return 0;
		}
		Node nd = pq.top();pq.pop();

		if(i > R[nd.u]){
			cout<<"No\n";
			return 0;
		}

		ret[i] = nd.u;
		pos[nd.u] = i;
	}

	rep(i,1,n){
		int u = topo[i];
		for(auto v:e[u])if(pos[u] > pos[v]){
			swap(ret[pos[u]],ret[pos[v]]);
			swap(pos[u],pos[v]);
		}
	}

	rep(i,1,n)assert(pos[i] >= L[i] && pos[i] <= R[i]);

	cout<<"Yes\n";
	rep(i,1,n)cout<<pos[i]<<" ";
	
    return 0;
}

Submission Info

Judge Result