#914085 (C++17) No.241 出席番号(1)

提出ソース

結果

問題	No.241 出席番号(1)
ユーザー	Gandalfr
提出日時	2023-09-19 12:26:03
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	13 ms / 2,000 ms
コード長	11,412 bytes
コンパイル時間	4,567 ms
コンパイル使用メモリ	216,868 KB
実行使用メモリ	4,384 KB
最終ジャッジ日時	2023-09-19 12:26:11
合計ジャッジ時間	7,097 ms
ジャッジサーバーID （参考情報）	judge13 / judge14

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,384 KB
testcase_01	AC	2 ms 4,384 KB
testcase_02	AC	3 ms 4,376 KB
testcase_03	AC	2 ms 4,380 KB
testcase_04	AC	3 ms 4,380 KB
testcase_05	AC	2 ms 4,376 KB
testcase_06	AC	2 ms 4,380 KB
testcase_07	AC	2 ms 4,380 KB
testcase_08	AC	2 ms 4,380 KB
testcase_09	AC	2 ms 4,380 KB
testcase_10	AC	2 ms 4,380 KB
testcase_11	AC	2 ms 4,376 KB
testcase_12	AC	2 ms 4,380 KB
testcase_13	AC	2 ms 4,384 KB
testcase_14	AC	8 ms 4,380 KB
testcase_15	AC	8 ms 4,380 KB
testcase_16	AC	2 ms 4,380 KB
testcase_17	AC	2 ms 4,376 KB
testcase_18	AC	2 ms 4,380 KB
testcase_19	AC	1 ms 4,376 KB
testcase_20	AC	2 ms 4,380 KB
testcase_21	AC	2 ms 4,376 KB
testcase_22	AC	1 ms 4,376 KB
testcase_23	AC	4 ms 4,380 KB
testcase_24	AC	11 ms 4,376 KB
testcase_25	AC	10 ms 4,376 KB
testcase_26	AC	11 ms 4,380 KB
testcase_27	AC	11 ms 4,380 KB
testcase_28	AC	11 ms 4,376 KB
testcase_29	AC	13 ms 4,376 KB
testcase_30	AC	12 ms 4,376 KB
testcase_31	AC	11 ms 4,380 KB

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

ソースコード

raw source code

#line 1 "playspace/main.cpp"
#include <bits/stdc++.h>
#line 2 "library/gandalfr/graph/flow_graph.hpp"

#line 7 "library/gandalfr/graph/base_graph.hpp"

namespace internal {
template <class Weight> struct _base_edge {
    int v[2];
    Weight cost;
    int id;
    _base_edge() {}
    _base_edge(int from, int to, Weight cost, int id)
        : v{from, to}, cost(cost), id(id) {}

    // x から見た反対側の端点を返す
    int opp(int x) {
        if (x == v[0]) {
            return v[1];
        } else if (x == v[1]) {
            return v[0];
        } else {
            std::abort();
        }
    }

    friend std::ostream &operator<<(std::ostream &os,
                                    const _base_edge<Weight> &e) {
        e.print(os);
        return os;
    }

  protected:
    virtual void print(std::ostream &os) const = 0;
};
} // namespace internal

template <class Weight> struct edge : public internal::_base_edge<Weight> {
    using internal::_base_edge<Weight>::_base_edge;

    edge reverse() const {
        return {this->v[1], this->v[0], this->cost, this->id};
    }

  protected:
    void print(std::ostream &os) const override {
        os << this->v[0] << " " << this->v[1] << " " << this->cost;
    }
};

template <> struct edge<int> : public internal::_base_edge<int> {
    static inline const int cost = 1;
    using internal::_base_edge<int>::_base_edge;
    edge(int _from, int _to, int _id) : _base_edge<int>(_from, _to, 1, _id) {}

    edge reverse() const { return {v[1], v[0], 1, id}; }

  protected:
    void print(std::ostream &os) const override {
        os << this->v[0] << " " << this->v[1];
    }
};

template <class Weight, class Flow>
struct flow_edge : public internal::_base_edge<Weight> {
    Weight res, cap;

    flow_edge(int from, int to, Flow res, Flow cap, int id)
        : internal::_base_edge<Weight>(from, to, 1, id), res(res), cap(cap) {}
    flow_edge(int from, int to, Flow res, Flow cap, Weight cost, int id)
        : internal::_base_edge<Weight>(from, to, cost, id), res(res), cap(cap) {
    }

    flow_edge reverse() const {
        return {this->v[1], this->v[0], cap - res, cap, this->cost, this->id};
    }

    // x から見た残余
    Flow residual(int x) const {
        if (x == this->v[0]) {
            return res;
        } else if (x == this->v[1]) {
            return cap - res;
        } else {
            std::abort();
        }
    }

    // x から見て残余がゼロか？
    Flow is_full(int x) const {
        if (x == this->v[0]) {
            return res == 0;
        } else if (x == this->v[1]) {
            return cap - res == 0;
        } else {
            std::abort();
        }
    }

    // x から流量を d だけ追加
    void add_flow(int x, Flow d) {
        if (x == this->v[0]) {
            res -= d;
        } else if (x == this->v[1]) {
            res += d;
        } else {
            std::abort();
        }
    }

  protected:
    void print(std::ostream &os) const override {
        os << this->v[0] << " " << this->v[1] << " " << cap - res << "/" << cap;
    }
};

namespace internal {

template <typename Edge> class _base_graph {
  protected:
    int N;
    std::vector<std::vector<Edge *>> G;
    std::vector<std::unique_ptr<Edge>> E;

  public:
    _base_graph(){};
    _base_graph(int n) : N(n), G(n){};
    _base_graph(int n, int m) : N(n), G(n) { E.reserve(m); };

    /**
     * @return ノードの数
     */
    int count_nodes() const { return N; }

    /**
     * @return 辺の数
     */
    int count_edges() const { return E.size(); }

    /**
     * @param n ノード番号
     * @return ノード n からの隣接頂点のリストの const 参照
     */
    const std::vector<Edge *> &operator[](int n) const { return G[n]; }

    /**
     * @return グラフ全体の辺のポインタのリストの const 参照
     */
    const std::vector<std::unique_ptr<Edge>> &edges() const { return E; }

    void print() const {
        std::cout << this->N << " " << this->E.size() << std::endl;
        for (auto &e : this->E)
            std::cout << *e << std::endl;
    }
};
} // namespace internal
#line 4 "library/gandalfr/graph/flow_graph.hpp"

template <typename Weight, typename Flow>
class flow_graph : public internal::_base_graph<flow_edge<Weight, Flow>> {
  public:
    using internal::_base_graph<flow_edge<Weight, Flow>>::_base_graph;
    flow_graph(const flow_graph &other) : flow_graph(other.N) {
        for (auto &e : other.E) {
            add_edge(*e);
        }
    }

    /**
     * @brief ノードの数をn個まで増やす
     * @param n サイズ
     * @attention 今のノード数より小さい数を渡したとき、変化なし
     */
    void expand(int n) {
        if (n <= this->N)
            return;
        this->N = n;
        this->G.resize(n);
    }

    /**
     * @attention 辺の id は保持される
     */
    void add_edge(const flow_edge<Weight, Flow> &e) {
        this->E.emplace_back(std::make_unique<flow_edge<Weight, Flow>>(e));
        this->G[e.v[0]].push_back(this->E.back().get());
        this->G[e.v[1]].push_back(this->E.back().get());
    }

    /**
     * @attention 辺の id は、(現在の辺の本数)番目 が振られる
     */
    void add_edge(int from, int to, Flow capacity) {
        int id = (int)this->E.size();
        flow_edge<Weight, Flow> e(from, to, capacity, capacity, id);
        this->E.emplace_back(std::make_unique<flow_edge<Weight, Flow>>(e));
        this->G[from].push_back(this->E.back().get());
        this->G[to].push_back(this->E.back().get());
    }

    Flow Ford_Fulkerson(int s, int t) {
        static_assert(std::is_integral<Flow>::value,
                      "Flow must be an integer type");
        Flow flow = 0;
        while (true) {
            std::vector<bool> vis(this->N, false);
            auto dfs = [&](auto self, int cur, Flow f) -> Flow {
                if (cur == t)
                    return f;
                vis[cur] = true;
                for (auto &e : this->G[cur]) {
                    if (vis[e->opp(cur)] || e->is_full(cur))
                        continue;
                    Flow tmp = self(self, e->opp(cur),
                                    std::min<Flow>(e->residual(cur), f));
                    if (tmp > static_cast<Flow>(0)) {
                        e->add_flow(cur, tmp);
                        return tmp;
                    }
                }
                return static_cast<Flow>(0);
            };
            Flow inc = dfs(dfs, s, std::numeric_limits<Flow>::max());
            if (inc == 0)
                break;
            flow += inc;
        }
        return flow;
    }

    Flow Dinic(int s, int t) {
        const int invalid = std::numeric_limits<int>::max();
        Flow flow = 0;
        while (true) {
            std::vector<int> dist(this->N, invalid);
            dist[s] = 0;
            std::queue<int> q;
            q.push(s);
            while(!q.empty()) {
                int cur = q.front();
                q.pop();
                for (auto &e: this->G[cur]) {
                    int to = e->opp(cur);
                    if (dist[to] != invalid || e->is_full(cur))
                        continue;
                    dist[to] = dist[cur] + 1;
                    q.push(to);
                }
            }
            if (dist[t] == invalid) break;

            while (true) {
                auto dfs = [&](auto self, int cur, Flow f) -> Flow {
                    if (cur == s)
                        return f;
                    for (auto &e : this->G[cur]) {
                        int to = e->opp(cur);
                        if (dist[to] != dist[cur] - 1)
                            continue;
                        Flow tmp = self(self, to,
                                        std::min<Flow>(e->residual(to), f));
                        if (tmp > static_cast<Flow>(0)) {
                            e->add_flow(to, tmp);
                            return tmp;
                        }
                    }
                    return static_cast<Flow>(0);
                };
                Flow inc = dfs(dfs, t, std::numeric_limits<Flow>::max());
                if (inc == 0)
                    break;
                flow += inc;
            }
        }
        return flow;
    }

};
#line 8 "library/gandalfr/other/io_supporter.hpp"

template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
    for (int i = 0; i < (int)v.size(); i++)
        os << v[i] << (i + 1 != (int)v.size() ? " " : "");
    return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::set<T> &st) {
    for (const T &x : st) {
        std::cout << x << " ";
    }
    return os;
}

template <typename T>
std::ostream &operator<<(std::ostream &os, const std::multiset<T> &st) {
    for (const T &x : st) {
        std::cout << x << " ";
    }
    return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::deque<T> &dq) {
    for (const T &x : dq) {
        std::cout << x << " ";
    }
    return os;
}
template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2> &p) {
    os << p.first << ' ' << p.second;
    return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, std::queue<T> &q) {
    int sz = q.size();
    while (--sz) {
        os << q.front() << ' ';
        q.push(q.front());
        q.pop();
    }
    os << q.front();
    q.push(q.front());
    q.pop();
    return os;
}

template <typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
    for (T &in : v)
        is >> in;
    return is;
}
template <typename T1, typename T2>
std::istream &operator>>(std::istream &is, std::pair<T1, T2> &p) {
    is >> p.first >> p.second;
    return is;
}
#line 4 "playspace/main.cpp"
using namespace std;
using ll = long long;
const int INF = 1001001001;
const ll INFLL = 1001001001001001001;
const ll MOD  = 1000000007;
const ll _MOD = 998244353;
#define rep(i, j, n) for(ll i = (ll)(j); i < (ll)(n); i++)
#define rrep(i, j, n) for(ll i = (ll)(n-1); i >= (ll)(j); i--)
#define all(a) (a).begin(),(a).end()
#define debug(a) std::cerr << #a << ": " << a << std::endl
#define LF cout << endl
#ifdef ENABLE_MULTI_FOR
#define mrep(it, mr) for(multi_iter it(mr); !it.fin(); ++it)
#endif
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
void Yes(bool ok){ std::cout << (ok ? "Yes" : "No") << std::endl; }

int main(void){

    int N;
    cin >> N;
    flow_graph<int, int> G(2 * N + 2, N * N);
    rep(i,0,N) {
        G.add_edge(0, i + 1, 1);
        G.add_edge(i + N + 1, 2 * N + 1, 1);
    }
    rep(i,0,N) {
        int a;
        cin >> a;
        rep(j,0,N) {
            if (j == a) continue;
            G.add_edge(i + 1, j + N + 1, 1);
        }
    }

    int mch = G.Dinic(0, 2 * N + 1);
    
    if (mch != N) {
        cout << -1 << endl;
    } else {
        vector<int> ans(N);
        rep(i,0,N) {
            for (auto &e: G[i + 1]) {
                if (e->is_full(i + 1)) {
                    ans[i] = e->v[1] - N - 1;
                }
            }
        }
        cout << ans << endl;
    }

}

yukicoder

結果

テストケース

ソースコード