首页 > 其他 > 详细

[Keyence Programming Contest 2020 E] Bichromization

时间:2020-02-26 00:57:53      阅读:57      评论:0      收藏:0      [点我收藏+]

标签:turn   dig   因此   priority   只需要   pla   

传送门

按照 \(d_i\) 从大到小依次考虑每个点。发现我们可以通过将某些边调整为 \(10^9\) 来 “封死” 这条边,从而使得每个点 \(i\) 至多与一个 \(d_j\leq d_i\)\(j\) 相邻。可以证明取最小的一个 \(j\) 不会导致无解。

此时,若 \(d_j < d_i\),则 \((i, j)\) 应设为 \(d_i-d_j\),并使两点同色。此时,由于封死了其余 \(d_j\leq d_i\) 的边,且 \(d_j>d_i\) 的边,要么已经被考虑 \(j\) 时封死了,要么 \((i, j)\) 同色,不会影响答案。因此我们只需要找到 \(j\) 点的答案,即可自动完成 \(i\) 点。

否则,\((i, j)\) 应设为 \(d_i\),并使两点异色。此时,他们以及对应连通块的条件都已经满足。若不存在这样的 \(j\),则无解。

#include <bits/stdc++.h>
#define R register
#define mp make_pair
#define ll long long
#define pii pair<int, int>
using namespace std;
const int N = 110000, M = N << 2, inf = 1e9;

int n, m, d[N], nxt[M], to[M], noedg = 1, hd[N], val[M], tag[N];
priority_queue<pii> que;
char s[N];

struct DSU {
//
int fa[M];

inline void init() {
    for (R int i = 1; i <= n * 2; ++i) fa[i] = i;
    return;
}

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

inline void unite(int x, int y) {
    fa[find(x)] = find(y);
    return;
}
//
} dsu;

inline void addEdg(int x, int y) {
    nxt[++noedg] = hd[x], hd[x] = noedg, to[noedg] = y;
    nxt[++noedg] = hd[y], hd[y] = noedg, to[noedg] = x;
    return;
}

template <class T>
inline void read(T &x) {
    x = 0;
    char ch = getchar(), w = 0;
    while (!isdigit(ch)) w = (ch == '-'), ch = getchar();
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    x = w ? -x : x;
    return;
}

inline char rev(char ch) {
    return ch == 'B' ? 'W' : 'B';
}

int main() {
    int x, y;
    read(n), read(m);
    for (R int i = 1; i <= n; ++i) read(d[i]), que.push(mp(d[i], i));
    for (R int i = 1; i <= m; ++i) read(x), read(y), addEdg(x, y);
    dsu.init();
    while (que.size()) {
        int now = que.top().second, pos = now; 
        que.pop();
        if (tag[now]) {
            for (R int i = hd[now]; i; i = nxt[i])
                if (!val[i >> 1]) val[i >> 1] = inf;
            continue;
        }
        for (R int i = hd[now], v; i; i = nxt[i])
            v = to[i], pos = d[v] <= d[pos] ? v : pos;
        if (pos == now) return printf("-1\n"), 0;
        if (d[pos] < d[now]) {
            dsu.unite(pos, now), dsu.unite(pos + n, now + n);
            for (R int i = hd[now], v; i; i = nxt[i]) {
                if ((v = to[i]) == pos)
                    val[i >> 1] = d[now] - d[v];
                else if (!val[i >> 1])
                    val[i >> 1] = inf;
            }
        }
        else {
            dsu.unite(pos + n, now), dsu.unite(pos, now + n);
            tag[pos] = 1;
            for (R int i = hd[now], v; i; i = nxt[i]) {
                if ((v = to[i]) == pos)
                    val[i >> 1] = d[now];
                else if (!val[i >> 1])
                    val[i >> 1] = inf;
            }
        }
    }
    for (R int i = 1; i <= n; ++i) {
        if (s[i]) continue;
        int k = dsu.find(i);
        if (k > n) {
            if (!s[k - n]) s[k - n] = 'W';
            s[i] = rev(s[k - n]);
        }
        else {
            if (!s[k]) s[k] = 'W';
            s[i] = s[k];
        }
    }
    printf("%s\n", s + 1);
    for (R int i = 1; i <= m; ++i) printf("%d\n", val[i]);
    return 0;
}

[Keyence Programming Contest 2020 E] Bichromization

标签:turn   dig   因此   priority   只需要   pla   

原文:https://www.cnblogs.com/suwakow/p/12364794.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号