M_sea

CF547D Mike and Fish
CodeForcesLuogu分析感觉和 Points and Segments 那题有点像。把 $x$ 相同的点...
扫描右侧二维码阅读全文
10
2019/05

CF547D Mike and Fish

CodeForces

Luogu

分析

感觉和 Points and Segments 那题有点像。

把 $x$ 相同的点两两配对连边, $y$ 相同的点两两配对连边。

然后二分图染色即可。

当然可能会多出一些没连边的点,正好对应相差 $1$ 。

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400000+10;

struct Edge { int v,nxt; } e[N<<1];
int head[N];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

int col[N],lst[2][N];

inline void dfs(int u,int c) {
    col[u]=c;
    for (re int i=head[u];i;i=e[i].nxt)
        if (col[e[i].v]==-1) dfs(e[i].v,c^1);
}

int main() {
    int n=read();
    for (re int i=1;i<=n;++i) {
        int x=read(),y=read();
        if (lst[0][x]) {
            addEdge(i,lst[0][x]),addEdge(lst[0][x],i);
            lst[0][x]=0;
        }
        else lst[0][x]=i;
        if (lst[1][y]) {
            addEdge(i,lst[1][y]),addEdge(lst[1][y],i);
            lst[1][y]=0;
        }
        else lst[1][y]=i;
    }
    memset(col,-1,sizeof(col));
    for (re int i=1;i<=n;++i)
        if (col[i]==-1) dfs(i,0);
    for (re int i=1;i<=n;++i) putchar("br"[col[i]]);
    return 0;
}
最后修改:2019 年 05 月 26 日 10 : 07 PM

发表评论