General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
187571709 Practice:
DaiRuiChen007
1635E - 53 C++14 (GCC 6-32) Accepted 202 ms 14920 KB 2023-01-02 05:43:14 2023-01-02 05:43:14
→ Source
// LUOGU_RID: 98475634
#include<bits/stdc++.h>
#define L false
#define R true
#define MEET 2
#define LEAVE 1
using namespace std;
const int MAXN=2e5+1;
struct node {
	int u,v,w;
};
vector <node> edges;
int dsu[MAXN<<1];
inline int find(int x) {
	if(dsu[x]==x) return x;
	return dsu[x]=find(dsu[x]);
}
inline void merge(int u,int v) {
	dsu[find(u)]=find(v);
}
bool dir[MAXN],ch[MAXN<<1],vis[MAXN<<1];
vector <int> G[MAXN];
int deg[MAXN],pos[MAXN];
signed main() {
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=2*n;++i) dsu[i]=i;
	for(int i=1;i<=m;++i) {
		int w,u,v;
		scanf("%d%d%d",&w,&u,&v);
		edges.push_back((node){u,v,w});
		merge(u,v+n),merge(u+n,v);
	}
	for(int i=1;i<=n;++i) {
		if(find(i)==find(i+n)) {
			puts("NO");
			return 0;
		}
		int x=find(i),y=find(i+n);
		if(!vis[x]) {
			dir[i]=L;
			vis[x]=vis[y]=true;
			ch[x]=true,ch[y]=false;
		} else dir[i]=ch[x]?L:R;
	}
	for(auto e:edges) {
		int u=e.u,v=e.v,w=e.w;
		if(w==LEAVE) {
			if(dir[u]==L&&dir[v]==R) G[u].push_back(v),++deg[v];
			if(dir[u]==R&&dir[v]==L) G[v].push_back(u),++deg[u];
		}
		if(w==MEET) {
			if(dir[u]==L&&dir[v]==R) G[v].push_back(u),++deg[u];
			if(dir[u]==R&&dir[v]==L) G[u].push_back(v),++deg[v];
		}
	}
	queue <int> q;
	vector <int> ord;
	for(int i=1;i<=n;++i) if(!deg[i]) q.push(i);
	while(!q.empty()) {
		int p=q.front(); q.pop();
		ord.push_back(p);
		for(int v:G[p]) {
			--deg[v];
			if(!deg[v]) q.push(v);
		}
	}
	if((int)(ord.size())<n) {
		puts("NO");
		return 0;
	}
	for(int i=0;i<n;++i) pos[ord[i]]=i;
	puts("YES");
	for(int i=1;i<=n;++i) printf("%c %d\n",dir[i]==L?'L':'R',pos[i]);
	return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details