CF704D Captain America

很套路的题吧。。唯一毒瘤的地方在于不是很有源汇上下界限最大流。。

考虑把坐标离散化一下，然后 $(x,y)$ 这个点就看成 $x \to y$ 连下界 0 上界 1 的边，表示这个点是选优秀的颜色还是不优秀的。

然后对于一个限制，我们考虑这上面有 $x$ 个点，其中两种点的差不能超过 $y$ ，这种时候这条直线上能够选择的优酷的点是在一个范围内的。推下式子可以得到，下界是 $\lceil \frac{x - y}{2} \rceil$ 上界是 $\lfloor \frac{x+y}{2} \rfloor$ 。

然后跑有源汇上下界最大流就好了。每个中间的 $x \to y$ 流量为 1 就意味着这个点选择 优秀的颜色。

。。这题爆 int 感觉很无解。。最后果断 #define int long long

记住判断一下，如果下界都大于上界了，也就是说存在必然不能满足的点，直接输出 -1 就好。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "bitset"
#include "queue"
using namespace std;
#define MAXN 400006
#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define P 998244353
typedef long long ll;
int n , m , z , q , r , b;
int A[MAXN];

struct Node {
    struct Edge *firstEdge, *currEdge;
    long long level, extraIn;
} N[MAXN + 2];

struct Edge {
    Node *from, *to;
    int cap, flow;
    Edge *next, *revEdge;

    Edge(Node *from, Node *to, int cap) : from(from), to(to), cap(cap), flow(0), next(from->firstEdge) {}
};

struct Dinic {
    bool makeLevelGraph(Node *s, Node *t, int n) {
        for (int i = 0; i < n; i++) {
            N[i].level = 0;
            N[i].currEdge = N[i].firstEdge;
        }

        std::queue<Node *> q;
        q.push(s);

        s->level = 1;

        while (!q.empty()) {
            Node *v = q.front();
            q.pop();

            for (Edge *e = v->firstEdge; e; e = e->next) {
                if (e->flow < e->cap && !e->to->level) {
                    e->to->level = v->level + 1;
                    if (e->to == t)
                        return true;
                    else
                        q.push(e->to);
                }
            }
        }

        return false;
    }

    int findPath(Node *s, Node *t, int limit = INT_MAX) {
        if (s == t)
            return limit;

        for (Edge *&e = s->currEdge; e; e = e->next) {
            if (e->to->level == s->level + 1 && e->flow < e->cap) {
                int flow = findPath(e->to, t, std::min(limit, e->cap - e->flow));
                if (flow) {
                    e->flow += flow;
                    e->revEdge->flow -= flow;
                    return flow;
                }
            }
        }

        return 0;
    }

    int operator()(int s, int t, int n) {
        int res = 0;
        while (makeLevelGraph(&N[s], &N[t], n)) {
            int flow;
            while ((flow = findPath(&N[s], &N[t])) > 0) res += flow;
        }

        return res;
    }
} dinic;

inline Edge* addEdge(int from, int to, int cap) {
    N[from].firstEdge = new Edge(&N[from], &N[to], cap);
    Edge* ret = N[from].firstEdge;
    N[to].firstEdge = new Edge(&N[to], &N[from], 0);

    N[from].firstEdge->revEdge = N[to].firstEdge;
    N[to].firstEdge->revEdge = N[from].firstEdge;
    return ret;
}

inline Edge* addEdge(int from, int to, int lower, int upper) {
//    printf("%d %d %d %d\n",from,to,lower,upper);
    int cap = upper - lower;
    Edge* ret = addEdge(from, to, cap);

    N[to].extraIn += lower;
    N[from].extraIn -= lower;
    return ret;
}

// 原图的节点编号为 [1, n]
// 超级源点、汇点会占用 0 与 n + 1
//
// 所以总节点要开 MAXN + 2
inline int flow(int s, int t, int n) {
    addEdge(t, s, INT_MAX);

    int S = 0, T = n + 1;

    int sum = 0;
    for (int i = 1; i <= n; i++) {
        if (N[i].extraIn > 0) {
            addEdge(S, i, N[i].extraIn);
            sum += N[i].extraIn;
        } else if (N[i].extraIn < 0) {
            addEdge(i, T, -N[i].extraIn);
        }
    }

    // 求可行流，满足下界
    int flow = dinic(S, T, n + 2);
    if (flow < sum)
        return -1;

    // 直接增广得到最大流
    return dinic(s, t, n + 2);
}

struct dun {
    int x , y;
    void rd( ) { scanf("%lld%lld",&x,&y); }
} D[MAXN] ;
Edge* ec[MAXN];
vi xs , ys;
int hx[MAXN] , hy[MAXN];
int strx[MAXN] , stry[MAXN];
void solve() {
//    freopen("input","r",stdin);
//    freopen("ot","w",stdout);
    cin >> n >> m >> r >> b;
    int S = 2 * n + 1 , T = 2 * n + 2;
    rep( i , 1 , n ) D[i].rd() , xs.pb( D[i].x ) , ys.pb( D[i].y );
    sort( all( xs ) ) , sort( all( ys ) );
    xs.resize( unique( all( xs ) ) - xs.begin() );
    ys.resize( unique( all( ys ) ) - ys.begin() );
    rep( i , 1 , n ) D[i].x = lower_bound( all( xs ) , D[i].x ) - xs.begin() + 1 , ++ hx[D[i].x];
    rep( i , 1 , n ) D[i].y = lower_bound( all( ys ) , D[i].y ) - ys.begin() + 1 , ++ hy[D[i].y];
    rep( i , 1 , n ) ec[i] = addEdge( D[i].x , D[i].y + xs.size() , 0 , 1 );
    int t , l , d;
    for( int i = 1 ; i <= xs.size() ; ++ i ) strx[i] = n;
    for( int i = 1 ; i <= ys.size() ; ++ i ) stry[i] = n;
    rep( i , 1 , m ) {
        scanf("%lld%lld%lld",&t,&l,&d);
        if( t == 1 ) {
            int L = lower_bound( all( xs ) , l ) - xs.begin() + 1;
            if( L - 1 >= xs.size() || xs[L - 1] != l ) continue;
            strx[L] = min( strx[L] , d );
        } else {
            int L = lower_bound( all( ys ) , l ) - ys.begin() + 1;
            if( L - 1 >= ys.size() || ys[L - 1] != l ) continue;
            stry[L] = min( stry[L] , d );
        }
    }
//    rep( i , 1 , n ) printf("%d %d\n",D[i].x,D[i].y);
//    rep( i , 1 , xs.size() ) printf("On x %d there are %d points with strict %d\n",i,hx[i],strx[i]);
//    rep( i , 1 , ys.size() ) printf("On y %d there are %d points with strict %d\n",i,hy[i],stry[i]);
    rep( i , 1 , xs.size() ) {
        int c = hx[i] , d = strx[i];
        int l = ( c - d + 1 ) / 2 , r = ( c + d ) / 2;
        if( l > r ) return puts("-1") , void();
        addEdge( S , i , ( c - d + 1 ) / 2 , ( c + d ) / 2 );
    }
    rep( i , 1 , ys.size() ) {
        int c = hy[i] , d = stry[i];
        int l = ( c - d + 1 ) / 2 , r = ( c + d ) / 2;
        if( l > r ) return puts("-1") , void();
        addEdge( i + xs.size() , T , ( c - d + 1 ) / 2 , ( c + d ) / 2 );
    }
    int ans = flow( S , T , 2 * n + 2 );
    char mn = ( r < b ? 'r' : 'b' ) , mx = ( r < b ? 'b' : 'r' );
    int Mn = min( r , b ) , Mx = max( r , b );
    long long res = 0;
    if( ~ans ) {
        vi re;
        for( int i = 1 ; i <= n ; ++ i )
            if( ec[i] -> flow )
                re.pb( mn ) , res += Mn;
            else re.pb( mx ) , res += Mx;
        printf("%lld\n",res);
        for( auto t : re ) putchar(t); puts("");
    } else puts("-1");
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}