裏紙

ほぼ競プロ、たまに日記

CF 871 C - Points, Lines and Ready-made Titles

問題

Problem - C - Codeforces

問題概要

2次元平面上に点がn個ある。i番目の点の座標は(x_i , y_i)である。各点に対して、x軸に平行な線を描く、y軸に平行な線を描く、何も描かないのどれかの操作を選ぶことが出来る。 このn個の点から描かれた線を平面上に描かれた画像と見なすと、画像は何通りの可能性があるか、10^9 + 7で割った余りを答えよ。

  •  1 \le n \le 10^5
  •  -10^9 \le x_i , y_i \le 10^9
  • 全ての点は平面上で異なる位置にある。

イデア

全ての点に対して操作は3通りあるので、全体としては3^n通りあるけど、同じy座標の点がそれぞれ横に線引いたら被るしどうやってその重複する数え上げを排除しよう...とか悩んでいた。

点を基準にするのではなく、出来上がる画像を基準にして考える。線が発生し得るx座標に対して小さい順にX_1 , X_2, \ldots , X_a、同様にy座標に対してもY_1 , Y_2 , \ldots , Y_bとして、これらを頂点とし、このxとyを結ぶ辺として各点を考える。

上のグラフを考えると、今回できる操作は各辺に対してその辺をつなぐ2点のどちらかをonに出来るということに対応する。連結成分ごとに考えてみると(連結成分の頂点数をVとする)、連結成分が木なら、全部の頂点をonにするということ以外は出来るので、2^V - 1通りが出来る。木ではなく、閉路が1つでもできるなら全ての通りを実現できるので2^V通りが出来る。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

using pi = pair<int,int>;

const ll mod = 1e9+7;
const int N = 222222;

ll pw[N];

vector<int> G[N];
bool vis[N]={};
int cv;
set<pi> ce;
void dfs(int v)
{
    vis[v] = true;
    ++cv;
    for(int e:G[v])
    {
        ce.insert({min(e,v),max(e,v)});
        if(!vis[e]) dfs(e);
    }
}

int main()
{
    pw[0] = 1;
    for(int i=1; i<N; ++i) pw[i] = (pw[i-1]*2)%mod;

    int n;
    scanf(" %d", &n);

    vector<int> x(n),y(n),xx,yy;
    rep(i,n)
    {
        scanf(" %d %d", &x[i], &y[i]);
        xx.pb(x[i]);
        yy.pb(y[i]);
    }

    sort(all(xx));
    xx.erase(unique(all(xx)),xx.end());
    sort(all(yy));
    yy.erase(unique(all(yy)),yy.end());

    int a = xx.size(), b = yy.size();
    rep(i,n)
    {
        int vx = lower_bound(all(xx),x[i])-xx.begin();
        int vy = lower_bound(all(yy),y[i])-yy.begin()+a;

        G[vx].pb(vy);
        G[vy].pb(vx);
    }

    ll ans = 1;
    rep(i,a+b)
    {
        if(vis[i]) continue;
        cv = 0;
        ce.clear();

        dfs(i);
        int E = ce.size();
        if(E>=cv) (ans*=pw[cv])%=mod;
        else (ans*=pw[cv]-1)%=mod;
    }

    printf("%lld\n", ans);
    return 0;
}