Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
38080 baka24 【BJ】T2 C++ 通过 100 34 MS 888 KB 2883 2025-06-12 18:19:21

Tests(12/12):


#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define inx(u) int I=h[(u)],v=edge[I].v,w=edge[I].w;I;I=edge[I].nx,v=edge[I].v,w=edge[I].w int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=300010,inf=1e7,INF=1e9; struct Edge{int v,nx,w;}edge[MAXN<<1];int h[MAXN],CNT=1,cur[MAXN];void add_side(int u,int v,int w){ // cout<<u<<" "<<v<<" "<<(w>10000?-1:w)<<endl; edge[++CNT]={v,cur[u],w};cur[u]=CNT;edge[++CNT]={u,cur[v],0};cur[v]=CNT;} int S,T; int n,m,fa[MAXN],k,d[MAXN],l[MAXN],r[MAXN],as[MAXN]; struct dinic{ int res,h[MAXN],dis[MAXN]; queue<int>Q; bool bfs(){ for(int i=1;i<=k;i++)h[i]=cur[i],dis[i]=0; dis[S]=1;Q.push(S); while(!Q.empty()){ int u=Q.front();Q.pop(); for(inx(u))if(w&&!dis[v]){ dis[v]=dis[u]+1; Q.push(v); } } return dis[T]>1; } int dfs(int u,int sum){ if(u==T||!sum)return sum; int num=sum; for(inx(u)){h[u]=I; if(dis[v]!=dis[u]+1)continue; int tmp=dfs(v,min(num,w)); edge[I].w-=tmp,edge[I^1].w+=tmp; num-=tmp; if(!num)break; } return sum-num; } int qry(){ res=0; while(bfs())res+=dfs(S,INF); return res; } }D; void adside(int u,int v,int l,int r){ add_side(u,v,r-l); d[v]-=l,d[u]+=l; } int fid(int x){return fa[x]==x?x:fa[x]=fid(fa[x]);} void slv(){ n=read(),m=read(); for(int i=1;i<=n+m;i++)fa[i]=i; k=n; for(int i=1;i<=m;i++){ int op=read(); if(op==1){ k++; int x=fid(read()),y=fid(read()); adside(x,k,0,inf); adside(y,k,0,inf); fa[x]=fa[y]=k; } if(op==2){ k++; int x=read(),y=fid(x); adside(y,k,0,inf); adside(y,x,0,1); fa[y]=k; as[x]=CNT; } if(op==3){ k++; int x=read(),L=read(),R=read(); x=fid(x); adside(fid(x),k,L,R); fa[x]=k; } } for(int i=1;i<=n;i++)if(!as[i]){ adside(fid(i),i,0,1),as[i]=CNT; } S=k+1,T=k+2; int tmp=0; for(int i=1;i<=k;i++)if(d[i]>0)add_side(i,T,d[i]),tmp+=d[i];else if(d[i]<0)add_side(S,i,-d[i]); k+=2; if(D.qry()!=tmp){puts("NO");} else{ puts("YES"); for(int i=1;i<=n;i++)if(edge[as[i]].w)putchar('R'); else putchar('B'); } } signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); slv(); return 0; }


测评信息: