結果

問題 No.654 Air E869120
ユーザー 横山緑
提出日時 2025-03-26 11:38:51
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 10 ms / 2,000 ms
コード長 4,864 bytes
コンパイル時間 4,478 ms
コンパイル使用メモリ 302,016 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-26 11:38:58
合計ジャッジ時間 6,099 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 2 "template.hpp"
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
template <class T>
concept Streamable = requires(ostream os, T &x) { os << x; };
template <class mint>
concept is_modint = requires(mint &x) {
    { x.val() } -> std::convertible_to<int>;
};
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...)
#endif

template <Streamable T> void print_one(const T &value) { cout << value; }
template <is_modint T> void print_one(const T &value) { cout << value.val(); }
void print() { cout << '\n'; }
template <class T, class... Ts> void print(const T &a, const Ts &...b) {
    print_one(a);
    ((cout << ' ', print_one(b)), ...);
    cout << '\n';
}
template <ranges::range Iterable>
    requires(!Streamable<Iterable>)
void print(const Iterable &v) {
    for(auto it = v.begin(); it != v.end(); ++it) {
        if(it != v.begin())
            cout << " ";
        print_one(*it);
    }
    cout << '\n';
}
using ll = long long;
using vl = vector<ll>;
using vll = vector<vl>;
using P = pair<ll, ll>;
#define all(v) v.begin(), v.end()
template <typename T> inline bool chmax(T &a, T b) {
    return ((a < b) ? (a = b, true) : (false));
}
template <typename T> inline bool chmin(T &a, T b) {
    return ((a > b) ? (a = b, true) : (false));
}
// https://trap.jp/post/1224/
template <class... T> constexpr auto min(T... a) {
    return min(initializer_list<common_type_t<T...>>{a...});
}
template <class... T> constexpr auto max(T... a) {
    return max(initializer_list<common_type_t<T...>>{a...});
}
template <class... T> void input(T &...a) { (cin >> ... >> a); }
template <class T> void input(vector<T> &a) {
    for(T &x : a)
        cin >> x;
}
#define INT(...)                                                               \
    int __VA_ARGS__;                                                           \
    input(__VA_ARGS__)
#define LL(...)                                                                \
    long long __VA_ARGS__;                                                     \
    input(__VA_ARGS__)
#define STR(...)                                                               \
    string __VA_ARGS__;                                                        \
    input(__VA_ARGS__)
#define REP1(a) for(ll i = 0; i < a; i++)
#define REP2(i, a) for(ll i = 0; i < a; i++)
#define REP3(i, a, b) for(ll i = a; i < b; i++)
#define REP4(i, a, b, c) for(ll i = a; i < b; i += c)
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)
#define rep1(i, n) for(ll i = 1; i <= ((ll)n); ++i)

ll inf = 3e18;
vl dx = {1, -1, 0, 0};
vl dy = {0, 0, 1, -1};
#line 2 "/home/y_midori/cp/a.cpp"
template <class T>
T edmands_karp(vector<unordered_map<int, T>> &graph, int source, int sink) {
    assert(source != sink);
    T flow = 0;
    vector<int> par(graph.size()), q = par;
    for(;;) {
        fill(all(par), -1);
        par[source] = 0;
        int ptr = 1;
        q[0] = source;
        rep(i, 0, ptr) {
            int x = q[i];
            for(auto e : graph[x]) {
                if(par[e.first] == -1 and e.second > 0) {
                    par[e.first] = x;
                    q[ptr++] = e.first;
                    if(e.first == sink)
                        goto out;
                }
            }
        }
        return flow;
    out:
        T inc = numeric_limits<T>::max();
        for(int y = sink; y != source; y = par[y])
            inc = min(inc, graph[par[y]][y]);
        flow += inc;
        for(int y = sink; y != source; y = par[y]) {
            int p = par[y];
            if((graph[p][y] -= inc) <= 0) {
                assert(graph[p][y] == 0);
                graph[p].erase(y);
            }
            graph[y][p] += inc;
        }
    }
}
struct flow_edge {
    int u, v, p, q;
    ll w;
};
int main() {
    INT(n, m, d);
    vector<flow_edge> g(m);
    using pii = pair<int, int>;
    map<pii, int> id;
    vector<set<int>> t(n);
    auto ins = [&](int loc, int time) {
        if(id.contains(pii(loc, time)))
            return;
        id[pii(loc, time)] = id.size();
        t[loc].insert(time);
    };
    ins(0, 0);
    ins(n - 1, numeric_limits<int>::max());
    rep(i, m) {
        INT(u, v, p, q, w);
        u--, v--, q += d;
        g[i] = flow_edge(u, v, p, q, w);
        ins(u, p);
        ins(v, q);
    }
    vector<unordered_map<int, ll>> graph(id.size());
    for(auto [u, v, p, q, w] : g) {
        graph[id[pii(u, p)]][id[pii(v, q)]] += w;
    }
    rep(i, 0, n) {
        for(auto itr = begin(t[i]); itr != end(t[i]); ++itr) {
            if(itr != begin(t[i])) {
                graph[id[pii(i, *prev(itr))]][id[pii(i, *itr)]] = inf;
            }
        }
    }
    ll ans = edmands_karp(graph, 0, 1);
    print(ans);
}
0