結果

問題 No.654 Air E869120
コンテスト
ユーザー startcpp
提出日時 2026-08-12 20:13:35
言語 C++14
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 2 ms / 2,000 ms
+ 986µs
コード長 2,446 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 889 ms
コンパイル使用メモリ 115,256 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2026-08-12 20:13:45
合計ジャッジ時間 2,993 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// 計算量は怪しい
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <atcoder/maxflow>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;
using namespace atcoder;

const int INF = 1e+14;
int n, m, d;
int U[1000], V[1000], p[1000], q[1000], w[1000];
vector<int> v2q[1000];
vector<int> v2p[1000];
int rs[2001];

//mode: 0 (in edge), 1 (out edge)
int toId(int v, int mode, int t) {
    int id;
    if (mode == 0) {
        id = lower_bound(v2q[v].begin(), v2q[v].end(), t) - v2q[v].begin();
    }
    else {
        id = lower_bound(v2p[v].begin(), v2p[v].end(), t) - v2p[v].begin();
    }
    return rs[mode * n + v] + id;
}

//[l, r)
int toL(int v, int mode) { return toId(v, mode, -1); }
int toR(int v, int mode) { return toId(v, mode, INF); }

signed main() {
    int i;

    cin >> n >> m >> d;
    rep(i, m) {
        cin >> U[i] >> V[i] >> p[i] >> q[i] >> w[i];
        U[i]--; V[i]--;
        v2p[U[i]].push_back(p[i]);
        v2q[V[i]].push_back(q[i]);
    }

    rep(i, n) {
        sort(v2p[i].begin(), v2p[i].end());
        v2p[i].erase(unique(v2p[i].begin(), v2p[i].end()), v2p[i].end());
        sort(v2q[i].begin(), v2q[i].end());
        v2q[i].erase(unique(v2q[i].begin(), v2q[i].end()), v2q[i].end());
    }

    rs[0] = 0;
    rep(i, n) rs[i + 1] = rs[i] + v2q[i].size();
    rep(i, n) rs[n + i + 1] = rs[n + i] + v2p[i].size();

    mf_graph<int> g(rs[2 * n] + 2);
    int s = rs[2 * n], t = s + 1;

    // 頂点間
    rep(i, m) {
        int u = toId(U[i], 1, p[i]);
        int v = toId(V[i], 0, q[i]);
        g.add_edge(u, v, w[i]);
    }

    // 頂点内
    rep(i, n) {
        int id1 = toL(i, 0);
        int id2 = toL(i, 1);
        int j, k = 0;
        for (j = 0; j < v2q[i].size(); j++) {
            for (; k < v2p[i].size(); k++) {
                if (v2q[i][j] + d <= v2p[i][k]) {
                    int u = id1 + j;
                    int v = id2 + k;
                    g.add_edge(u, v, INF);
                    break;
                }
            }
        }
        for (j = 0; j + 1 < v2p[i].size(); j++) {
            g.add_edge(id2 + j, id2 + j + 1, INF);
        }
    }

    int idS = toL(0, 1);
    rep(i, v2p[0].size()) {
        g.add_edge(s, idS + i, INF);
    }

    int idT = toL(n - 1, 0);
    rep(i, v2q[n - 1].size()) {
        g.add_edge(idT + i, t, INF);
    }

    cout << g.flow(s, t) << endl;
    return 0;
}
0