結果

問題 No.654 Air E869120
ユーザー eggkid6eggkid6
提出日時 2023-11-14 20:52:03
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 6,080 bytes
コンパイル時間 2,669 ms
コンパイル使用メモリ 241,508 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-26 03:56:47
合計ジャッジ時間 3,998 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 7 ms
5,376 KB
testcase_11 AC 7 ms
5,376 KB
testcase_12 AC 7 ms
5,376 KB
testcase_13 AC 7 ms
5,376 KB
testcase_14 AC 7 ms
5,376 KB
testcase_15 AC 7 ms
5,376 KB
testcase_16 AC 10 ms
5,376 KB
testcase_17 AC 12 ms
5,376 KB
testcase_18 AC 11 ms
5,376 KB
testcase_19 AC 10 ms
5,376 KB
testcase_20 AC 5 ms
5,376 KB
testcase_21 AC 6 ms
5,376 KB
testcase_22 AC 5 ms
5,376 KB
testcase_23 AC 5 ms
5,376 KB
testcase_24 AC 5 ms
5,376 KB
testcase_25 AC 4 ms
5,376 KB
testcase_26 AC 4 ms
5,376 KB
testcase_27 AC 4 ms
5,376 KB
testcase_28 AC 4 ms
5,376 KB
testcase_29 AC 4 ms
5,376 KB
testcase_30 AC 4 ms
5,376 KB
testcase_31 AC 4 ms
5,376 KB
testcase_32 AC 3 ms
5,376 KB
testcase_33 AC 4 ms
5,376 KB
testcase_34 AC 4 ms
5,376 KB
testcase_35 AC 2 ms
5,376 KB
testcase_36 AC 2 ms
5,376 KB
testcase_37 AC 2 ms
5,376 KB
testcase_38 AC 1 ms
5,376 KB
testcase_39 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for (ll i = s; i < ll(n); ++i)
#define per(i, n) for (ll i = ll(n) - 1; i >= 0; --i)
#define per2(i, s, n) for (ll i = ll(n) - 1; i >= s; --i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define fi first
#define se second
#define pf push_front
#define pb push_back
#define ppf pop_front
#define ppb pop_back
#define ef emplace_front
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define fix(n) cout << fixed << setprecision(n);
using namespace std;
using ll = long long;
using ld = long double;
using V = vector<ll>;
using P = pair<ll,ll>;
using M = map<ll,ll>;
using S = set<ll>;
using Q = queue<ll>;
using PQ = priority_queue<ll>;
using VV = vector<V>;
using VVV = vector<VV>;
using VVVV = vector<VVV>;
using VVVVV = vector<VVVV>;
using VVVVVV = vector<VVVVV>;
using VS = vector<string>;
using VP = vector<P>;
using VB = vector<bool>;
template<class T>
using PQG = priority_queue<T, vector<T>, greater<T>>;
template<class T>
bool constexpr chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T>
bool constexpr chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<class T>
void constexpr Vin(vector<T> &v) {
    for (T &a : v) cin >> a;
}
template<class T>
void constexpr Vout(vector<T> &v) {
    for (T &a : v) cout << a << " ";
    cout << endl;
}
template<class T>
void constexpr Voutl(vector<T> &v) {
    for (T &a : v) cout << a << endl;
}
const ll power(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}
const ll mpower(ll a, ll b, const ll &m) {
    a %= m;
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
const string yes[] = {"no", "yes"};
const string Yes[] = {"No", "Yes"};
const string YES[] = {"NO", "YES"};
const int H[] = {1, 0, -1, 0};
const int W[] = {0, 1, 0, -1};
constexpr ll mod = 998244353;
constexpr ll MOD = 1000000007;
constexpr ll INF = 1LL << 60;

template <class T>
struct MaximumFlow {
    struct Edge {
        int to, rev;
        T cap;
        Edge(int to, int rev, T cap) : to(to), rev(rev), cap(cap) {}
    };
    struct edge {
        int from, to;
        T cap, flow;
        edge(int from, int to, T cap, T flow) : from(from), to(to), cap(cap), flow(flow) {}
    };
    int n;
    vector<vector<Edge>> G;
    vector<int> level, iter;
    vector<pair<int,int>> pos;
    queue<int> q;
    MaximumFlow() : n(0) {}
    MaximumFlow(int n) : n(n), G(n), level(n), iter(n) {}
    void add_edge(int from, int to, T cap) {
        int from_id = G[from].size();
        int to_id = G[to].size() + (from == to);
        pos.emplace_back(from, from_id);
        G[from].emplace_back(to, to_id, cap);
        G[to].emplace_back(from, from_id, 0);
    }
    T dfs(int v, int t, T up) {
        if (v == t) return up;
        T res = 0;
        for (int& i = iter[v]; i < int(G[v].size()); ++i) {
            Edge& e = G[v][i];
            if (level[v] >= level[e.to] || e.cap == 0) continue;
            T f = dfs(e.to, t, min(up - res, e.cap));
            if (f == 0) continue;
            e.cap -= f;
            G[e.to][e.rev].cap += f;
            res += f;
            if (res == up) return res;
        }
        return res;
    }
    T flow(int s, int t) {
        return flow(s, t, numeric_limits<T>::max());
    }
    T flow(int s, int t, T flow_limit) {
        T flow = 0;
        while (true) {
            fill(level.begin(), level.end(), -1);
            q.push(s);
            level[s] = 0;
            while (q.size()) {
                int v = q.front();
                q.pop();
                for (Edge& e : G[v]) {
                    if (level[e.to] != -1 || e.cap == 0) continue;
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
            if (level[t] == -1) return flow;
            fill(iter.begin(), iter.end(), 0);
            T f = dfs(s, t, flow_limit - flow);
            if (f == 0) return flow;
            flow += f;
        }
    }
    edge get_edge(int i) {
        Edge& e = G[pos[i].first][pos[i].second];
        Edge& re = G[e.to][e.rev];
        return edge{pos[i].first, e.to, e.cap + re.cap, re.cap};
    }
    vector<edge> edges() {
        vector<edge> res;
        for (int i = 0; i < int(pos.size()); ++i) {
            res.push_back(get_edge(i));
        }
        return res;
    }
    vector<bool> min_cut(int s) {
        vector<bool> res(n);
        q.push(s);
        res[s] = true;
        while (q.size()) {
            int v = q.front();
            q.pop();
            for (Edge& e : G[v]) {
                if (e.cap && !res[e.to]) {
                    res[e.to] = true;
                    q.push(e.to);
                }
            }
        }
        return res;
    }
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n, m, d;
    cin >> n >> m >> d;
    MaximumFlow<ll> mf(m * 2 + 2);
    vector<S> time(n);
    time[0].insert(0);
    time[n - 1].insert(power(10, 9));
    vector<tuple<ll,ll,ll,ll,ll>> jet(m);
    rep(i, m) {
        ll u, v, p, q, w;
        cin >> u >> v >> p >> q >> w;
        --u, --v;
        time[u].insert(p);
        time[v].insert(min(power(10, 9), q + d));
        jet[i] = {u, v, p, q, w};
    }
    map<P,int> mp;
    ll idx = 0;
    rep(i, n) {
        for (ll t : time[i]) {
            mp[{i, t}] = idx++;
        }
    }
    rep(i, n) {
        ll pre = -1;
        for (ll t : time[i]) {
            if (pre != -1) {
                mf.add_edge(mp[{i, pre}], mp[{i, t}], INF);
            }
            pre = t;
        }
    }
    rep(i, m) {
        ll u, v, p, q, w;
        tie(u, v, p, q, w) = jet[i];
        mf.add_edge(mp[{u, p}], mp[{v, min(power(10, 9), q + d)}], w);
    }
    cout << mf.flow(0, idx - 1) << '\n';
}
0