結果

問題 No.2675 KUMA
コンテスト
ユーザー NokonoKotlin
提出日時 2024-03-13 20:09:54
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 7 ms / 2,000 ms
コード長 6,840 bytes
コンパイル時間 2,533 ms
コンパイル使用メモリ 159,840 KB
実行使用メモリ 28,132 KB
最終ジャッジ日時 2024-09-29 23:01:35
合計ジャッジ時間 4,083 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

// reviewer2

// include
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
typedef long long LL;
typedef vector<long long> vll;

typedef pair<long long, long long> pll;
typedef pair<long long, long long> PLL;
typedef vector<pair<ll, ll> > vpll;

// container util
//------------------------------------------
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MP make_pair
// repetition
//------------------------------------------
#define FOR(i, a, b) for (long long i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

#define ENDL cout << endl;
#define CIN(a) REP(i, a.size()) cin >> a[i];

struct BipartiteMatching {
    vector<vector<int> > graph;
    vector<int> match, alive, used;
    int timestamp;

    BipartiteMatching(int n) : graph(n), alive(n, 1), used(n, 0), match(n, -1), timestamp(0) {}

    void add_edge(int u, int v) {
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    bool dfs(int idx) {
        used[idx] = timestamp;
        for (auto& to : graph[idx]) {
            int to_match = match[to];
            if (alive[to] == 0) continue;
            if (to_match == -1 || (used[to_match] != timestamp && dfs(to_match))) {
                match[idx] = to;
                match[to] = idx;
                return true;
            }
        }
        return false;
    }

    int bipartite_matching() {
        int ret = 0;
        for (int i = 0; i < graph.size(); i++) {
            if (alive[i] == 0) continue;
            if (match[i] == -1) {
                ++timestamp;
                ret += dfs(i);
            }
        }
        return ret;
    }

    void output() {
        for (int i = 0; i < graph.size(); i++) {
            if (i < match[i]) {
                cout << i << "-" << match[i] << endl;
            }
        }
    }
};

/*
    入力で与えられる UMA の座標を +10 ぐらいしておく
    座標(index)は (x , y) とする
*/

// [i][j] := (i,j) に 何番目の UMA がいるか (1-index)
// KUMA が置いてあるなら -1 とする
ll grid[2000][2000];

int N;
vector<pair<int, int> > UMA;

// pair(i,j) := i,j を同時に観測する
// ようなペア群 を全て列挙する
vector<vpll> matching;

vpll tmp;
vll tmp2;

void rec(int i, vpll& match_now, vll& memo) {
    // i := 何番目の UMA まで調べたか
    // match_now := 現在マッチしている UMA のペア
    // memo[i] := UMA i がすでに他の UMA とマッチしているか (マッチしている (true) なら無視する)
    // (＊＊＊＊＊連結成分 3 以上のマッチは意味がない＊＊＊＊＊)
    if (i == N) {
        matching.push_back(match_now);
        return;
    }
    rec(i + 1, match_now, memo);
    if (memo[i]) return;
    memo[i] = 1;
    int x = UMA[i].first;
    int y = UMA[i].second;
    vpll pr = {{x, y + 2}, {x + 2, y}, {x, y - 2}, {x - 2, y}};  // 同時に監視される UMA の座標候補

    for (pll pos : pr) {
        int id = grid[pos.first][pos.second] - 1;
        if (id > i) {
            // pos に、自分より番号が大きい UMA がいるなら、マッチングできる
            if (memo[id] == 0) {
                match_now.emplace_back(i, id);
                memo[id] = 1;
                rec(i + 1, match_now, memo);
                match_now.pop_back();
                memo[id] = 0;
            }
        }
    }
    memo[i] = 0;
}

const int BORDER = 2000;
int toint(pll p) {
    return p.first * BORDER + p.second;
}

pll topair(int id) {
    return {id / BORDER, id % BORDER};
}

int COMPRESS[5000000];  // 座標(toint) の座圧結果は毎回書き換えるので、COMPRESS を使い回してOK

int main() {
    cin >> N;
    UMA.resize(N);
    REP(i, N) {
        ll x, y;
        cin >> x >> y;
        x += 20;
        y += 20;
        UMA[i] = {x, y};
        grid[x][y] = i + 1;
    }

    // 使ったかどうかのメモ用
    tmp2.resize(N + 1, 0);
    // マッチングを
    rec(0, tmp, tmp2);

    sort(RALL(matching), [&](vpll& a, vpll& b) { return a.size() < b.size(); });
    ;

    vpll dire = {{-1, 2}, {-1, -2}, {1, 2}, {1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};

    for (const vpll& Pairs : matching) {
        set<int> Units;  //単体の UMA
        REP(i, N)
        Units.insert(i);
        for (pll p : Pairs) {
            Units.erase(p.first);
            Units.erase(p.second);
        }

        set<int> A;  // このスコープで関係ある座標たちの ID(後で座圧する)
        for (pll p : Pairs) {
            A.insert(toint(UMA[p.first]));
            A.insert(toint(UMA[p.second]));
        }
        for (ll p : Units) A.insert(toint(UMA[p]));

        REP(i, N) {
            // 8 方向見る
            for (pll nx : dire) {
                A.insert(toint(MP(UMA[i].first + nx.first, UMA[i].second + nx.second)));
            }
        }

        int id = 0;
        for (ll x : A) COMPRESS[x] = id++;  // COMPRESS には 0 ~ |A|-1 がメモされる

        // 辺を貼りましょう。
        BipartiteMatching F(A.size() + Pairs.size());  // A & pair_id & snk & src

        for (int i : Units) {
            // 8 方向見る
            for (pll nx : dire) {
                ll x = UMA[i].first + nx.first;
                ll y = UMA[i].second + nx.second;
                if (grid[x][y] >= 1) continue;
                F.add_edge(COMPRESS[toint(UMA[i])], COMPRESS[toint(MP(x, y))]);
            }
        }

        // ペアの方は、元の UMA の id とは別で id を用意する(これは COMPRESS しなくて OK )

        int pair_id = A.size();
        for (pll p : Pairs) {
            set<int> KMA_excluded;  // ペアの両方の 8 方向をいれていき、重複したものが候補になる

            // まずは first から
            for (pll nx : dire) {
                ll x = UMA[p.first].first + nx.first;
                ll y = UMA[p.first].second + nx.second;
                KMA_excluded.insert(toint(MP(x, y)));
            }

            // 次は second
            for (pll nx : dire) {
                ll x = UMA[p.second].first + nx.first;
                ll y = UMA[p.second].second + nx.second;
                // 重複 = 候補である
                if (KMA_excluded.count(toint(MP(x, y)))) {
                    if (grid[x][y] >= 1) continue;
                    F.add_edge(pair_id, COMPRESS[toint(MP(x, y))]);
                }
            }
            pair_id++;
        }

        int mxf = F.bipartite_matching();
        if (mxf == N - Pairs.size()) {
            cout << mxf << endl;
            return 0;
        }
    }

    // 無理だった場合
    cout << -1 << endl;
    return 0;
}
0