547D Mike and Fish

传送门

分析

见正睿10.3笔记

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
int n,m,col[400200],cnt,Ans[400200];
multiset<pair<int,int> >v[400200];
inline void go(int x){
    while(!v[x].empty()){
      pair<int,int> a=*v[x].begin();
      int to=a.first,id=a.second;
      v[x].erase(v[x].find(make_pair(to,id)));
      v[to].erase(v[to].find(make_pair(x,id)));      
      go(to);
      col[++cnt]=id;
    }
}
int main(){
    int i,j,k,x,y;
    scanf("%d",&n);
    m=n;
    for(i=1;i<=n;i++){
      scanf("%d%d",&x,&y);
      v[x].insert(make_pair(y+200001,i));
      v[y+200001].insert(make_pair(x,i));
    }
    for(i=1;i<=400002;i++)
      if(v[i].size()%2){
          if(i<200001){
            m++;
            v[i].insert(make_pair(400002,m));
            v[400002].insert(make_pair(i,m));
        }else {
          m++;
            v[i].insert(make_pair(200001,m));
            v[200001].insert(make_pair(i,m));
        }
      }
    for(i=1;i<=400002;i++)go(i);
    for(i=1;i<=cnt;i++)Ans[col[i]]=i%2;
    for(i=1;i<=n;i++){
      if(Ans[i])printf("r");
        else printf("b");
    }
    return 0;
}