#948680 (C++17) No.2675 KUMA

提出ソース

結果

問題	No.2675 KUMA
ユーザー	👑 nu50218
提出日時	2024-02-08 17:50:12
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	9 ms / 2,000 ms
コード長	13,129 bytes
コンパイル時間	2,223 ms
コンパイル使用メモリ	154,932 KB
実行使用メモリ	26,080 KB
最終ジャッジ日時	2024-02-08 17:55:28
合計ジャッジ時間	3,675 ms
ジャッジサーバーID （参考情報）	judge13 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,676 KB
testcase_01	AC	2 ms 6,676 KB
testcase_02	AC	2 ms 6,676 KB
testcase_03	AC	3 ms 9,672 KB
testcase_04	AC	3 ms 9,692 KB
testcase_05	AC	5 ms 6,676 KB
testcase_06	AC	3 ms 6,676 KB
testcase_07	AC	2 ms 6,676 KB
testcase_08	AC	2 ms 6,676 KB
testcase_09	AC	9 ms 6,676 KB
testcase_10	AC	2 ms 6,676 KB
testcase_11	AC	3 ms 6,676 KB
testcase_12	AC	6 ms 26,080 KB
testcase_13	AC	5 ms 17,884 KB
testcase_14	AC	6 ms 26,080 KB
testcase_15	AC	3 ms 9,692 KB
testcase_16	AC	6 ms 24,044 KB
testcase_17	AC	2 ms 6,676 KB
testcase_18	AC	2 ms 6,676 KB
testcase_19	AC	2 ms 6,676 KB
testcase_20	AC	2 ms 6,676 KB
testcase_21	AC	2 ms 6,676 KB
testcase_22	AC	3 ms 6,676 KB
testcase_23	AC	2 ms 6,676 KB
testcase_24	AC	2 ms 6,676 KB
testcase_25	AC	2 ms 6,676 KB
testcase_26	AC	3 ms 6,676 KB
testcase_27	AC	2 ms 6,676 KB
testcase_28	AC	2 ms 6,676 KB
testcase_29	AC	2 ms 6,676 KB
testcase_30	AC	2 ms 6,676 KB
testcase_31	AC	2 ms 6,676 KB
testcase_32	AC	2 ms 6,676 KB
testcase_33	AC	2 ms 6,676 KB
testcase_34	AC	2 ms 6,676 KB
testcase_35	AC	2 ms 6,676 KB
testcase_36	AC	2 ms 6,676 KB
testcase_37	AC	2 ms 6,676 KB
testcase_38	AC	2 ms 6,676 KB
testcase_39	AC	2 ms 6,676 KB
testcase_40	AC	2 ms 6,676 KB
testcase_41	AC	2 ms 6,676 KB
testcase_42	AC	2 ms 6,676 KB
testcase_43	AC	2 ms 6,676 KB
testcase_44	AC	2 ms 6,676 KB
testcase_45	AC	3 ms 6,676 KB
testcase_46	AC	2 ms 6,676 KB
testcase_47	AC	3 ms 6,676 KB
testcase_48	AC	2 ms 6,676 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// 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];

/*
    T 型の フロー
    diff_ : T 型の a , b に対して、
        a ≠ b と abs(a - b) >= diff が同地となるような値

    例えば、int なら 1 , double なら 1e-12 とか
    (要するに、二分探索の閾値)

*/
template <class T = long long, T diff_ = 1>
struct mxfl {
   private:
    int edge_id_conuter = 0;
    struct edge {
        int from, to;
        T flow;
        int id;
        edge(int from, int to, int flow, int id) : from(from), to(to), flow(flow), id(id) {}
        edge* r_edge;  // 逆辺へのポインタ
    };

    vector<vector<edge*> > G;
    map<pair<int, int>, edge*> edges;

    // 何度も bfs するので、reach 配列を使い回したい
    int bfs_times = 0;                // 何回目の bfs か
    vector<pair<int, edge*> > reach;  // [x] := first が bfs_times と一致するなら、到達可能で、second が直前に使った辺のポインタ

    bool fast_input_mode = false;  // 多重辺を許す代わりに、add_edge が速くなる(bfs/dfs は遅くなる)

    // 多重辺を許す高速モード
    void fast_add_edge(int u, int v, T f) {
        edge* e = new edge(u, v, f, ++edge_id_conuter);
        edge* r_e = new edge(v, u, 0, ++edge_id_conuter);
        (*e).r_edge = r_e;
        (*r_e).r_edge = e;
        G[u].push_back(e);
        G[v].push_back(r_e);
    }

    vector<edge*> E;
    // 静的に add_edge する。その後 build する必要がある。
    void static_add_edge(int u, int v, T f) {
        edge* e = new edge(u, v, f, ++edge_id_conuter);
        edge* re = new edge(v, u, 0, ++edge_id_conuter);
        e->r_edge = re;
        re->r_edge = e;

        E.push_back(e);
        E.push_back(re);
    }

    bool first_commit = false;
    // build した後も、 log(E) で 辺を追加できる
    void dynamic_add_edge(int u, int v, T f) {
        // 最初は statix で追加した辺を map に格納する操作を行う
        if (first_commit)
            for (int x = 0; x < V; x++)
                for (edge* e : G[x]) edges[make_pair(e->from, e->to)] = e;
        first_commit = false;

        if (edges[make_pair(u, v)] != nullptr) {
            (*edges[make_pair(u, v)]).flow += f;
            return;
        }

        edge* e = new edge(u, v, f, ++edge_id_conuter);
        edge* r_e = new edge(v, u, 0, ++edge_id_conuter);
        (*e).r_edge = r_e;
        (*r_e).r_edge = e;
        edges[make_pair(u, v)] = e;
        edges[make_pair(v, u)] = r_e;
        G[u].push_back(e);
        G[v].push_back(r_e);
    }

   public:
    int V;

    mxfl(int V_, bool fst = false) : V(V_), G(V_), reach(V_, {-1, nullptr}), fast_input_mode(fst) {}
    ~mxfl() {
        for (vector<edge*>& v : G) {
            for (int i = int(v.size()) - 1; i >= 0; i--) delete v[i];
        }
    }

    void add_edge(int u, int v, T f) {
        if (fast_input_mode)
            fast_add_edge(u, v, f);  // 多重辺を許す高速モード
        else if (!built)
            static_add_edge(u, v, f);  // build 前は 静的モード
        else
            dynamic_add_edge(u, v, f);  // build 後は 動的モード
    }

    bool built = false;  // build したかどうか
    // 静的な add_edge のあとは build 必須
    void build() {
        if (built || fast_input_mode) return;
        built = true;
        if (E.size() == 0) return;

        sort(E.begin(), E.end(), [&](edge* a, edge* b) {
            if (a->from == b->from) {
                if (a->to == b->to)
                    return a->id < b->id;  // 宣言のタイミング
                else
                    return a->to < b->to;
            } else
                return a->from < b->from;
        });

        // 同じ頂点 (u-v) を結ぶものは、右のものにマージするとよい
        // 辺は宣言時に逆編とセットにしており、
        // 同じ頂点を結ぶ辺は「宣言順」にソートしており、逆転のポインタとのリンクも保持されたままである
        for (int i = 0; i < E.size(); i++) {
            if (i + 1 < E.size() && E[i]->from == E[i + 1]->from && E[i]->to == E[i + 1]->to) {
                E[i + 1]->flow += E[i]->flow;  // 右の辺も同じ頂点を結ぶなら、右にマージ
                delete E[i];
            } else
                G[E[i]->from].push_back(E[i]);
        }
        E.clear();
    }

    // s → t の流量 f そのパスを返す , 無理なら first が 0
    // パスを返すだけで、何も流さない
    pair<bool, vector<edge*> > FindPath(int s, int t, T f) {
        bfs_times++;
        vector<edge*> path;
        if (s == t) return {true, path};  // 未定義動作

        queue<int> q;
        q.push(s);
        bfs_times++;
        reach[s] = {bfs_times, nullptr};

        while (!q.empty()) {
            int now = q.front();
            q.pop();
            for (edge* e : G[now]) {
                if (e->flow >= f) {
                    if (reach[e->to].first != bfs_times) {
                        reach[e->to] = {bfs_times, e};
                        q.push(e->to);
                    }
                }
            }
        }

        if (reach[t].first != bfs_times) return {false, path};

        while (t != s) {
            path.push_back(reach[t].second);
            t = (reach[t].second)->from;
        }

        reverse(path.begin(), path.end());

        return {true, path};
    }

    // s → t の最大増加道 (パス) の容量を返す(にぶたん)
    T CalcMaxPath(int s, int t) {
        if (s == t) return 0;  //未定義
        T left = 0;
        T right = 1e9;

        while (right - left > diff_) {
            T mid = left + (right - left) / 2;
            queue<int> q;
            q.push(s);
            bfs_times++;
            reach[s] = {bfs_times, nullptr};

            while (!q.empty()) {
                int now = q.front();
                q.pop();
                for (edge* e : G[now]) {
                    if (e->flow >= mid) {
                        if (reach[e->to].first != bfs_times) {
                            reach[e->to] = {bfs_times, e};
                            q.push(e->to);
                        }
                    }
                }
            }
            if (reach[t].first == bfs_times)
                left = mid;
            else
                right = mid;
        }
        return left;
    }

    // 実際に s - t パスに f 流す
    // 流せないなら、流さない (パスに流すことに注意)
    bool Flow(int s, int t, T f) {
        auto tmp = FindPath(s, t, f);
        if (tmp.first) {
            for (edge* e : tmp.second) {
                e->flow -= f;
                e->r_edge->flow += f;
            }
        } else {
            return false;
        }

        return true;
    }

    // s → t に流せるだけ流す
    T MaxFlow(int s, int t) {
        T res = 0;
        while (true) {
            bool f = Flow(s, t, 1);
            if (!f) break;
            res += 1;
        }
        return res;
    }
};

/*
    入力で与えられる 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 = 1;
        for (ll x : A) COMPRESS[x] = id++;  // COMPRESS には 1 ~ |A| がメモされる

        // 辺を貼りましょう。
        mxfl<int> F(A.size() + Pairs.size() + 2);  // A & pair_id & snk & src
        int src = 0;
        int snk = A.size() + Pairs.size() + 1;

        for (int id : A) {
            pll p = topair(id);
            if (grid[p.first][p.second] >= 1) {  // 座標が UMA の場合
                F.add_edge(src, COMPRESS[id], 1);
            } else {
                F.add_edge(COMPRESS[id], snk, 1);
            }
        }

        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))], 1);
            }
        }

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

        int pair_id = A.size() + 1;
        for (pll p : Pairs) {
            F.add_edge(src, pair_id, 1);

            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))], 1);
                }
            }
            pair_id++;
        }

        F.build();
        int mxf = F.MaxFlow(src, snk);
        if (mxf == N - Pairs.size()) {
            cout << mxf << endl;
            return 0;
        }
    }

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

yukicoder

結果

テストケース

ソースコード