結果

問題 No.654 Air E869120
ユーザー pote-bokkopote-bokko
提出日時 2024-03-06 20:51:23
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,393 bytes
コンパイル時間 3,861 ms
コンパイル使用メモリ 234,568 KB
実行使用メモリ 6,676 KB
最終ジャッジ日時 2024-03-06 20:51:37
合計ジャッジ時間 11,992 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

// STLのインクルード
#include <bits/stdc++.h>
using namespace std;

// // ACLのインクルード(デフォルトはコメントアウト)
// #include <atcoder/all>
// using namespace atcoder;

// for文の略記
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define per(i, n) for (ll i = (ll)(n-1); i >= 0; i--)

// vectorのソート
#define all(x) x.begin(), x.end()

// 型の略記 (競プロならでは)
using ll = long long;
using pii = pair<ll, ll>;
using pll = pair<long long, long long>;
using vi = vector<ll>;
using vl = vector<long long>;
using vs = vector<string>;
using vc = vector<char>;
using vpii = vector<pair<ll, ll>>;
using vpll = vector<pair<long long, long long>>;
using vpsi = vector<pair<string, ll>>;
using vvi = vector<vector<ll>>;
using vvpii = vector<vector<pair<ll, ll>>>;
using vvl = vector<vector<long long>>;
using vvc = vector<vector<char>>;

template<typename T>
using priority_queue_up = priority_queue<T, vector<T>, greater<T>>;

// MOD計算で使う
#define MOD 1000000007
#define MOD2 998244353

// YES-NOで答える質問で使う(fがTrueならYes)
void cout_yn(bool f){
    if(f)cout << "Yes" << endl;
    else cout << "No" << endl;
}

// 木の前順走査
void dfs_preorder(ll v, vvi &tree, vi &output){
    output.push_back(v);
    rep(i, tree[v].size()){
        dfs_preorder(tree[v][i], tree, output);
    }
}
// 木の後順走査
void dfs_postorder(ll v, vvi &tree, vi &output){
    rep(i, tree[v].size()){
        dfs_preorder(tree[v][i], tree, output);
    }
    output.push_back(v);
}

// n頂点m辺の無向グラフを隣接リストで受け取る.
// 頂点番号は1-indexedとして入力される想定.
vector<vector<ll>> input_undir_graph(ll n, ll m){
    ll a, b;
    vector<vector<ll>> g(n);
    rep(i, m){
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b); // a->b へ向かう辺
        g[b].push_back(a); // b->a へ向かう辺
    }
    return g;
}

// n頂点m辺の有向グラフを隣接リストで受け取る.
// 頂点番号は1-indexedとして入力される想定.
vector<vector<ll>> input_dir_graph(ll n, ll m){
    ll a, b;
    vector<vector<ll>> g(n);
    rep(i, m){
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b); // a->b へ向かう辺
    }
    return g;
}

#define INF 1e9

struct edge{
    ll to, cap, q, rev;
};

vector<map<ll, vector<edge>>> G;
vector<map<ll, ll>> used;
ll n, m;
ll d;

void add_edge(ll u, ll v, ll c, ll p, ll q){
    G[u][p].push_back((edge){v, c, q, (ll)(G[v][q].size())});
    G[v][q].push_back((edge){u, 0, p, (ll)(G[u][p].size()-1)});
}

ll dfs(ll v, ll p, ll t, ll tq, ll f){
    if(v == t && p == tq){
        return f;
    }
    used[v][p] = 1;
    rep(i, G[v][p].size()){
        edge &e = G[v][p][i];
        if(e.cap > 0 && !used[e.to][e.q]){
            ll w = dfs(e.to, e.q, t, tq, min(f, e.cap));
            if(w > 0){
                G[v][p][i].cap -= w;
                G[e.to][e.q][e.rev].cap += w;
                return w;
            }
        }
    }
    return 0;
}

ll max_flow(ll s, ll p, ll t, ll tq){
    ll flow = 0;
    int cnt = 0;
    for(;;){
        for(ll i=0; i<n; i++)used[i].clear();
        ll f = dfs(s, p, t, tq, INF);
        if(f == 0)return flow;
        flow += f;
    }
}

// main関数
int main(void){
    cin >> n >> m >> d;
    G.resize(n);
    vector<set<ll>> time(n);
    used.resize(n);
    ll u, v, p, q, w;
    rep(i, m){
        cin >> u >> v >> p >> q >> w;
        u--, v--;
        add_edge(u, v, w, p, q+d);
        time[u].insert(p);
        time[v].insert(q+d);
    }
    rep(i, n){
        for(auto itr=time[i].begin(); itr!=--(time[i].end()); itr++){
            auto nx = itr; ++nx;
            add_edge(i, i, INF, *itr, *nx);
        }
    }
    /* cout << endl; */
    /* rep(i, n){ */
    /*     for(auto itr=G[i].begin(); itr!=G[i].end(); itr++){ */
    /*         auto nx = itr; ++nx; */
    /*         cout << i << " " << itr->first << " " << nx->first << endl; */
    /*         add_edge(i, i, INF, itr->first, nx->first); */
    /*         if(nx == G[i].end())break; */
    /*     } */
    /* } */
    rep(i, n){
        for(auto itr=G[i].begin(); itr!=G[i].end(); itr++){
            ll p = itr->first;
            vector<edge> E = itr->second;
        }
    }
    cout << max_flow(0, *time[0].begin(), n-1, *(--(time[n-1].end()))) << endl;
    return 0;
}
0