题解 P8326 【[COCI2021-2022#5] Fliper】

Leasier · 2023-11-03 16:31:19 · 题解

• 染色使得……相等 / 绝对值之差 \leq 1 等问题可以考虑欧拉回路。

首先可以根据挡板的到达关系建图：

• 设 i 表示挡板 i 朝下的一面，i' 表示挡板 i 朝上的一面。
• 我们建出的图由若干环和链构成。
• 我们的目标是给挡板染为四种颜色，令 i, i' 的颜色为挡板 i 的颜色，则我们希望每个环内每一种颜色的点的个数相同且为偶数。

若存在一个环的长度 \bmod \ 8 \neq 0，一定无解。

否则，我们来尝试构造一种方案。能染成四种颜色的必要条件为能染成两种颜色，于是我们先来考虑两种颜色怎么做。

直接在这张图上操作十分困难，考虑点边互化：我们尝试将一个挡板转化成一条边，边的颜色为挡板的颜色。

那么点是什么呢？注意到我们关心的是环内的颜色，考虑把环转化为点，则我们可以在一个挡板的两面所属的两个环对应的点间连边（这里我们先假定原图各连通块全都是环），则问题变为：

• 给定一张无向图。
• 给边黑白染色，使得每个点的出边中黑白颜色相等。

考虑给边定向，设黑边指向当前点、白边从当前点出发，则目标变为让每个点出入度相等。

“出入度相等”让我们想到有向图存在欧拉回路的判断条件，则我们直接在原无向图上跑出一条欧拉回路，对回路上的边黑白染色即可。

由于一个环对应点的度数为环上点数，则一定有解。

接下来考虑染成四种颜色怎么做。我们首先跑一遍两种颜色的情况，注意到把两种颜色的边各自构成的子图中每个点的度数分别 \bmod \ 4 = 0，于是在两个子图中各自再跑一遍欧拉回路黑白染色即可。

最后来考虑有连通块为链的情况。我们期待可以将其视作环处理，考虑建一个超级源点，钦定这些链上的点全部属于超级源点对应的环。若超级源点的度数 \bmod \ 8 \neq 0，我们强行连一些自环即可。

对 x, y 两维分别排序即可建出最初的图。时间复杂度为 O(n \log n)。

代码：

#include <algorithm>
#include <cstdio>

using namespace std;

typedef struct {
    int id;
    int type;
    int x;
    int y;
} Point;

typedef struct {
    int nxt;
    int end;
} Edge;

typedef struct {
    int cnt = 0;
    int head[1000007];
    int deg[1000007];
    Edge edge[2000007];

    inline void add_edge(int start, int end){
        cnt++;
        edge[cnt].nxt = head[start];
        head[start] = cnt;
        edge[cnt].end = end;
        deg[start]++;
    }
} Graph;

int top, loop = 0, op;
Graph g1, g2;
int stk[1000007], belong[1000007], cur_edge[1000007], color[500007], ans[500007];
bool vis1[1000007], vis2[1000007], vis3[1000007];
Point point[500007];

inline void init(int n, int m){
    op = 0;
    for (register int i = 0; i <= n; i++){
        cur_edge[i] = g2.head[i];
        vis2[i] = false;
    }
    for (register int i = 1; i <= m; i++){
        vis3[i] = false;
    }
}

inline int read(){
    int sign = 1, ans = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9'){
        if (ch == '-') sign = -sign;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9'){
        ans = ans * 10 + (ch ^ 48);
        ch = getchar();
    }
    return sign * ans;
}

inline int get_type(){
    char ch;
    do {
        ch = getchar();
    } while (ch != '/' && ch != '\\');
    return ch == '/' ? 0 : 1;
}

bool cmp1(const Point a, const Point b){
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

bool cmp2(const Point a, const Point b){
    if (a.y != b.y) return a.y < b.y;
    return a.x < b.x;
}

void dfs1(int u, int father){
    if (vis1[u]){
        loop++;
        while (top > 0){
            belong[stk[top--]] = loop;
        }
        return;
    }
    vis1[u] = true;
    stk[++top] = u;
    for (register int i = g1.head[u]; i != 0; i = g1.edge[i].nxt){
        int x = g1.edge[i].end;
        if (x != father) dfs1(x, u);
    }
}

void dfs2(int u){
    vis2[u] = true;
    for (register int i = cur_edge[u]; i != 0; i = g2.edge[cur_edge[u]].nxt){
        int id = (i + 1) / 2;
        cur_edge[u] = i;
        if (!vis3[id]){
            vis3[id] = true;
            dfs2(g2.edge[i].end);
            color[id] = op;
            op ^= 1;
        }
    }
}

void dfs3(int u, int goal){
    vis2[u] = true;
    for (register int i = cur_edge[u]; i != 0; i = g2.edge[cur_edge[u]].nxt){
        int id = (i + 1) / 2;
        cur_edge[u] = i;
        if (color[id] == goal && !vis3[id]){
            vis3[id] = true;
            dfs3(g2.edge[i].end, goal);
            ans[id] = ((goal << 1) | op) + 1;
            op ^= 1;
        }
    }
}

int main(){
    int n = read(), m = n * 2;
    for (register int i = 1; i <= n; i++){
        point[i].x = read();
        point[i].y = read();
        point[i].type = get_type();
        point[i].id = i;
    }
    sort(point + 1, point + n + 1, cmp1);
    for (register int i = 1; i <= n; ){
        int nxt = i;
        while (nxt < n && point[i].x == point[nxt + 1].x) nxt++;
        for (register int j = i; j < nxt; j++){
            g1.add_edge(point[j].id + n, point[j + 1].id);
            g1.add_edge(point[j + 1].id, point[j].id + n);
        }
        i = nxt + 1;
    }
    sort(point + 1, point + n + 1, cmp2);
    for (register int i = 1; i <= n; ){
        int nxt = i;
        while (nxt < n && point[i].y == point[nxt + 1].y) nxt++;
        for (register int j = i; j < nxt; j++){
            if (point[j].type == 0){
                if (point[j + 1].type == 0){
                    g1.add_edge(point[j].id, point[j + 1].id + n);
                    g1.add_edge(point[j + 1].id + n, point[j].id);
                } else {
                    g1.add_edge(point[j].id, point[j + 1].id);
                    g1.add_edge(point[j + 1].id, point[j].id);  
                }
            } else if (point[j + 1].type == 0){
                g1.add_edge(point[j].id + n, point[j + 1].id + n);
                g1.add_edge(point[j + 1].id + n, point[j].id + n);
            } else {
                g1.add_edge(point[j].id + n, point[j + 1].id);
                g1.add_edge(point[j + 1].id, point[j].id + n);
            }
        }
        i = nxt + 1;
    }
    for (register int i = 1; i <= m; i++){
        if (!vis1[i]){
            top = 0;
            dfs1(i, 0);
        }
    }
    for (register int i = 1; i <= n; i++){
        g2.add_edge(belong[i], belong[i + n]);
        g2.add_edge(belong[i + n], belong[i]);
    }
    for (register int i = 1; i <= loop; i++){
        if (g2.deg[i] % 8 != 0){
            printf("-1");
            return 0;
        }
    }
    while (g2.deg[0] % 8 != 0) g2.add_edge(0, 0);
    init(loop, n);
    for (register int i = 0; i <= loop; i++){
        if (!vis2[i]) dfs2(i);
    }
    init(loop, n);
    for (register int i = 0; i <= loop; i++){
        if (!vis2[i]) dfs3(i, 0);
    }
    init(loop, n);
    for (register int i = 0; i <= loop; i++){
        if (!vis2[i]) dfs3(i, 1);
    }
    for (register int i = 1; i <= n; i++){
        printf("%d ", ans[i]);
    }
    return 0;
}