結果
問題 | No.654 Air E869120 |
ユーザー | arktan763 |
提出日時 | 2019-08-14 12:05:32 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 5,092 bytes |
コンパイル時間 | 1,984 ms |
コンパイル使用メモリ | 190,208 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-19 13:46:23 |
合計ジャッジ時間 | 3,407 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 6 ms
5,376 KB |
testcase_11 | AC | 5 ms
5,376 KB |
testcase_12 | AC | 5 ms
5,376 KB |
testcase_13 | AC | 6 ms
5,376 KB |
testcase_14 | AC | 5 ms
5,376 KB |
testcase_15 | AC | 5 ms
5,376 KB |
testcase_16 | AC | 6 ms
5,376 KB |
testcase_17 | AC | 5 ms
5,376 KB |
testcase_18 | AC | 6 ms
5,376 KB |
testcase_19 | AC | 6 ms
5,376 KB |
testcase_20 | AC | 5 ms
5,376 KB |
testcase_21 | AC | 4 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 | 5 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 | 4 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 | 1 ms
5,376 KB |
testcase_37 | AC | 1 ms
5,376 KB |
testcase_38 | AC | 2 ms
5,376 KB |
testcase_39 | AC | 2 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long #define FOR(i, a, b) for(ll i = (a); i < (b); ++i) #define FORR(i, a, b) for(ll i = (a); i > (b); --i) #define REP(i, n) for(ll i = 0; i < (n); ++i) #define REPR(i, n) for(ll i = n; i >= 0; i--) #define FOREACH(x, a) for(auto &(x) : (a)) #define VECCIN(x) \ for(auto &youso_ : (x)) cin >> youso_ #define bitcnt __builtin_popcount #define SZ(x) ((ll)(x).size()) #define fi first #define se second #define All(a) (a).begin(), (a).end() template <typename T = long long> inline T IN() { T x; cin >> x; return (x); } inline void CIN() {} template <class Head, class... Tail> inline void CIN(Head &&head, Tail &&... tail) { cin >> head; CIN(move(tail)...); } #define CINT(...) \ int __VA_ARGS__; \ CIN(__VA_ARGS__) #define DCIN(...) \ double __VA_ARGS__; \ CIN(__VA_ARGS__) #define LCIN(...) \ ll __VA_ARGS__; \ CIN(__VA_ARGS__) #define SCIN(...) \ string __VA_ARGS__; \ CIN(__VA_ARGS__) #define Yes(a) cout << (a ? "Yes" : "No") << "\n" #define YES(a) cout << (a ? "YES" : "NO") << "\n" #define Printv(v) \ { \ FOREACH(x, v) { cout << x << " "; } \ cout << "\n"; \ } template <typename T = string> inline void eputs(T s) { cout << s << "\n"; exit(0); } template <typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); } template <typename T> using PQG = priority_queue<T, vector<T>, greater<T>>; template <typename T> using PQ = priority_queue<T>; typedef long long ll; typedef unsigned long long ul; typedef vector<ll> VL; typedef pair<ll, ll> PL; const int INF = 1e9; const int MOD = 1e9 + 7; const double PI = atan(1.0) * 4.0; // const int MOD = 998244353; const ll LINF = 9e18; const ll dx[] = {1, 0, -1, 0}; const ll dy[] = {0, 1, 0, -1}; void cinfast() { cin.tie(0); ios::sync_with_stdio(false); } struct edge { ll to, cap, rev; }; struct Mflow { vector<vector<edge>> G; VL level, iter; ll N; Mflow(ll size) : N(size) { init(size); }; void init(ll size) { G.resize(N); } void add_edge(ll from, ll to, ll cap) { G[from].push_back({to, cap, (ll)G[to].size()}); G[to].push_back({from, 0, (ll)G[from].size() - 1}); } void bfs(ll s) { level.assign(N, -1); queue<ll> q; level[s] = 0; q.push(s); while(!q.empty()) { ll now = q.front(); q.pop(); FOREACH(e, G[now]) { if(e.cap > 0 && level[e.to] == -1) { level[e.to] = level[now] + 1; q.push(e.to); } } } } ll dfs(ll now, ll t, ll f) { if(now == t) return f; for(ll &i = iter[now]; i < G[now].size(); i++) { edge &e = G[now][i]; if(e.cap > 0 && level[now] < level[e.to]) { ll d = dfs(e.to, t, min(f, e.cap)); if(d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } ll max_flow(ll s, ll t) { ll flow = 0; while(1) { bfs(s); if(level[t] < 0) return flow; iter.assign(N, 0); ll f; while((f = dfs(s, t, LINF)) > 0) { flow += f; } } } }; signed main() { LCIN(n, m, d); VL u(m), v(m), p(m), q(m), w(m); vector<PL> L; REP(i, m) { cin >> u[i] >> v[i] >> p[i] >> q[i] >> w[i]; q[i] += d; L.emplace_back(u[i], p[i]); L.emplace_back(v[i], q[i]); } sort(All(L)); Mflow mf(L.size() + 2); REP(i, m) { ll from = lower_bound(All(L), PL(u[i], p[i])) - L.begin(); ll to = lower_bound(All(L), PL(v[i], q[i])) - L.begin(); mf.add_edge(from, to, w[i]); } REP(i, L.size() - 1) { if(L[i + 1].fi == L[i].fi) mf.add_edge(i, i + 1, LINF); } REP(i, L.size()) { if(L[i].fi == 1) { mf.add_edge(L.size(), i, LINF); } if(L[i].fi == n) { mf.add_edge(i, L.size() + 1, LINF); } } ll ans = mf.max_flow(L.size(), L.size() + 1); cout << ans << "\n"; }