#1192843 (C++17) No.654 Air E869120

• 問題: No.654 Air E869120
• ユーザー: 小畑裕貴
• 提出日時: 2026-10-11 10:33:18
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 4,261 bytes
• コンパイル時間: 885 ms
• コンパイル使用メモリ: 157,492 KB
• 実行使用メモリ: 9,860 KB
• 最終ジャッジ日時: 2026-10-11 10:34:18
• 合計ジャッジ時間: 8,246 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_1

ファイルパターン	結果
sample	-- * 5
other	AC * 17 TLE * 1 -- * 17

ソースコード

#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <ctime>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define repb(i, e) for (int i = (int)(e); i >= 0; i--)
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vll = vector<long long>;
using vd = vector<double>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vvd = vector<vd>;
using vs = vector<string>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vc = vector<char>;
using vvc = vector<vc>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, long long>;
using pli = pair<long long, int>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vpil = vector<pil>;
using vpli = vector<pli>;

const double PI = acos(-1);
const ll MOD = 1000000007;
const ll MODL = 2147483647;
const int INF = 1000000007;
const ll INFL = 1LL<<60;

template <typename T> inline bool chmin(T &a, T b) {if (a > b) {a = b; return true;} return false;}
template <typename T> inline bool chmax(T &a, T b) {if (a < b) {a = b; return true;} return false;}
// template <typename T> T gcd(T a, T b) {if (a < b) swap(a, b); if (b == 0) return a; else return gcd(b, a%b);}
template <typename T> inline T ceil(T a, T b) {return (a+(b-1))/b;}
template <typename T> inline T floor(T a, T b) {return a/b;}
template <typename T> inline void add(T &a, T b, T m) {a = ((a % m + b % m)) % m;}
template <typename T> inline void sub(T &a, T b, T m) {a = ((a % m - b % m) + m) % m;}
template <typename T> inline void mul(T &a, T b, T m) {a = (((a % m + m) % m) * ((b % m) + m) % m) % m;}


struct Edge {
    int to, rev;
    ll cap;
};


class MaximumFlow {
    public:
    int size = 0;
    vb used;
    vector<vector<Edge>> G;

    MaximumFlow(int n) {
        init(n);
    }

    void init(int n) {
        size = n;
        used = vb(n);
        G = vector<vector<Edge>>(n);
        rep(i, n) G[i].clear();
    }

    void add_edge(int a, int b, ll c) {
        int Current_Ga = G[a].size();
        int Current_Gb = G[b].size();
        G[a].push_back(Edge{b, Current_Gb, c});
        G[b].push_back(Edge{a, Current_Ga, 0});
    }

    ll dfs(int pos, int goal, ll F) {
        if (pos == goal) return F;
        used[pos] = true;
        rep(i, G[pos].size()) {
            if (G[pos][i].cap == 0) continue;
            if (used[G[pos][i].to]) continue;
            ll flow = dfs(G[pos][i].to, goal, min(F, G[pos][i].cap));
            if (flow >= 1) {
                G[pos][i].cap -= flow;
                G[G[pos][i].to][G[pos][i].rev].cap += flow;
                return flow;
            }
        }
        return 0;
    }

    ll max_flow(int s, int t) {
        ll Total_Flow = 0;
        while (true) {
            rep(i, size) used[i] = false;
            ll F = dfs(s, t, 1e9);
            if (F == 0) break;
            Total_Flow += F;
        }
        return Total_Flow;
    }
};


int main() {
    int n, m, u, v, id1, id2;
    ll d, p, q, w;
    cin >> n >> m >> d;
    vvi time(n);
    vector<tuple<int, int, ll, ll, ll>> edge;
    rep(i, m) {
        cin >> u >> v >> p >> q >> w;
        u--;
        v--;
        time[u].push_back(p);
        time[v].push_back(q+d);
        edge.emplace_back(u, v, p, q+d, w);
    }
    vi now_id(n+1, 0);
    rep(i, n+1) {
        if (i != n) sort(all(time[i]));
        if (i != 0) now_id[i] = now_id[i-1] + time[i-1].size();
    }
    MaximumFlow MF(now_id[n]);
    rep(i, m) {
        auto [now, next, now_t, next_t, weight] = edge[i];
        id1 = lower_bound(all(time[now]), now_t) - time[now].begin();
        id2 = lower_bound(all(time[next]), next_t) - time[next].begin();
        MF.add_edge(now_id[now]+id1, now_id[next]+id2, weight);
    }
    rep(i, n) {
        rep(j, time[i].size()) {
            if (j + 1 != (int)(time[i].size())) MF.add_edge(now_id[i]+j, now_id[i]+j+1, INFL);
        }
    }
    cout << MF.max_flow(0, now_id[n]-1) << endl;
}