704D - Captain America - CodeForces Solution

#include<bits/stdc++.h>
#define ls(p) a[p].lc
#define rs(p) a[p].rc
#define fi first
#define se second
#define mkp make_pair
#define ll long long
#define pir pair<ll,ll>
#define pb push_back
using namespace std;
const ll maxn=15e5+10;
ll n,m,R,B,x[maxn],y[maxn],hx[maxn],hy[maxn],n1,n2,tot=1,head[maxn],q[maxn],l,r,dw[maxn],s,t,s1,t1,s2,t2,ans,dis[maxn];
ll px[maxn],py[maxn],cx[maxn],cy[maxn],cur[maxn],res[maxn],pid[maxn];
struct edge{
	ll v,w,nxt;
}e[maxn];
void ins(ll u,ll v,ll w){
	e[++tot]=(edge){v,w,head[u]};
	head[u]=tot;
}
bool bfs(){
	for(ll i=1;i<=n1+n2+4;i++) dis[i]=-1;
	dis[s]=0; q[l=r=1]=s;
	while(l<=r){
		ll u=q[l++];
		for(ll i=head[u];i;i=e[i].nxt){
			ll v=e[i].v;
			if(e[i].w&&dis[v]==-1){
				dis[v]=dis[u]+1;
				q[++r]=v;
			}
		}
	}
	return dis[t]!=-1;
}
ll dfs(ll u,ll flow){
	if(u==t) return flow;
	ll used=0;
	for(ll i=cur[u];i;cur[u]=i=e[i].nxt){
		ll v=e[i].v;
		if(dis[v]==dis[u]+1&&e[i].w){
			ll tmp=min(e[i].w,flow-used);
			tmp=dfs(v,tmp);
			used+=tmp;
			e[i].w-=tmp; e[i^1].w+=tmp;
			if(used==flow) break;
		}
	}
	return used;
}
ll dinic(){
	ll res=0;
	while(bfs()){
		for(ll i=1;i<=n1+n2+4;i++) cur[i]=head[i];
		ll tt=dfs(s,1e17);
		if(tt==0){
			printf("OMG"); exit(0);
		}
		res+=tt;
	} return res;
}
int main(){ 
	scanf("%lld%lld%lld%lld",&n,&m,&R,&B);
	ll flag=0;
	if(R>B) flag=1, swap(R,B);
	ans=R*n;
	for(ll i=1;i<=n;i++){
		scanf("%lld%lld",x+i,y+i);
		hx[++n1]=x[i], hy[++n2]=y[i];
	}
	sort(hx+1,hx+1+n1), sort(hy+1,hy+1+n2);
	n1=unique(hx+1,hx+1+n1)-hx-1, n2=unique(hy+1,hy+1+n2)-hy-1;
	for(ll i=1;i<=n;i++){
		x[i]=lower_bound(hx+1,hx+1+n1,x[i])-hx, y[i]=lower_bound(hy+1,hy+1+n2,y[i])-hy;
		ins(x[i],y[i]+n1,1), ins(y[i]+n1,x[i],0);
		pid[tot]=pid[tot-1]=i; ++cx[x[i]], ++cy[y[i]];
	}
	s1=n1+n2+1, t1=n1+n2+2, s2=n1+n2+3, t2=n1+n2+4;
	s=s2, t=t2;
	for(ll i=1;i<=n1;i++) px[i]=n;
	for(ll i=1;i<=n2;i++) py[i]=n;
	hx[n1+1]=1e17, hy[n2+1]=1e17;
	for(ll i=1;i<=m;i++){
		ll op,l,d;
		scanf("%lld%lld%lld",&op,&l,&d);
		if(op==1){
			ll id=lower_bound(hx+1,hx+2+n1,l)-hx;
			if(hx[id]==l) px[id]=min(px[id],d);
		} else{
			ll id=lower_bound(hy+1,hy+2+n2,l)-hy;
			if(hy[id]==l) py[id]=min(py[id],d);
		}
	}
	for(ll i=1;i<=n1;i++){
		ll vl=max(0ll,(cx[i]-px[i]+1)/2), vr=(cx[i]+px[i])/2;
		if(vl>vr){
			printf("-1"); return 0;
		}
		dw[s1]-=vl, dw[i]+=vl;
		if(vl==vr) continue;
		ins(s1,i,vr-vl), ins(i,s1,0);
	}
	for(ll i=1;i<=n2;i++){
		ll vl=max(0ll,(cy[i]-py[i]+1)/2), vr=(cy[i]+py[i])/2;
		if(vl>vr){
			printf("-1"); return 0;
		}
		dw[t1]+=vl, dw[i+n1]-=vl;
		if(vl==vr) continue;
		ins(i+n1,t1,vr-vl), ins(t1,i+n1,0);
	}
	ll sum=0;
	for(ll i=1;i<=n1+n2+2;i++)
		if(dw[i]){
			if(dw[i]>0) ins(s2,i,dw[i]), ins(i,s2,0), sum+=dw[i];
			else ins(i,t2,-dw[i]), ins(t2,i,0);
		}
	ins(t1,s1,1e17), ins(s1,t1,0);
	ll tmp=dinic();
	if(tmp!=sum){
		printf("-1"); return 0;
	}
	ans+=e[tot].w*(B-R);
	s=t1, t=s1;
	head[s]=e[head[s]].nxt;
	tmp=dinic();
	ans-=tmp*(B-R);
	printf("%lld\n",ans);
	for(ll u=1;u<=n1;u++){
		for(ll i=head[u];i;i=e[i].nxt){
			ll v=e[i].v;
			if(pid[i]) res[pid[i]]=(!e[i].w);
		}
	}
	for(ll i=1;i<=n;i++)
		printf("%c",((res[i]^flag)? 'b':'r'));
	return 0;
}