?
# | 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 |
// 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; }
?
?
?
?