結果
問題 | No.654 Air E869120 |
ユーザー | snbn |
提出日時 | 2020-04-30 00:53:06 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 20 ms / 2,000 ms |
コード長 | 4,666 bytes |
コンパイル時間 | 1,315 ms |
コンパイル使用メモリ | 118,956 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-30 17:48:59 |
合計ジャッジ時間 | 2,917 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 20 ms
5,248 KB |
testcase_11 | AC | 15 ms
5,248 KB |
testcase_12 | AC | 16 ms
5,248 KB |
testcase_13 | AC | 17 ms
5,248 KB |
testcase_14 | AC | 15 ms
5,248 KB |
testcase_15 | AC | 16 ms
5,248 KB |
testcase_16 | AC | 15 ms
5,248 KB |
testcase_17 | AC | 15 ms
5,248 KB |
testcase_18 | AC | 14 ms
5,248 KB |
testcase_19 | AC | 14 ms
5,248 KB |
testcase_20 | AC | 11 ms
5,248 KB |
testcase_21 | AC | 10 ms
5,248 KB |
testcase_22 | AC | 11 ms
5,248 KB |
testcase_23 | AC | 11 ms
5,248 KB |
testcase_24 | AC | 12 ms
5,248 KB |
testcase_25 | AC | 9 ms
5,248 KB |
testcase_26 | AC | 9 ms
5,248 KB |
testcase_27 | AC | 9 ms
5,248 KB |
testcase_28 | AC | 11 ms
5,248 KB |
testcase_29 | AC | 9 ms
5,248 KB |
testcase_30 | AC | 5 ms
5,248 KB |
testcase_31 | AC | 5 ms
5,248 KB |
testcase_32 | AC | 5 ms
5,248 KB |
testcase_33 | AC | 4 ms
5,248 KB |
testcase_34 | AC | 5 ms
5,248 KB |
testcase_35 | AC | 2 ms
5,248 KB |
testcase_36 | AC | 1 ms
5,248 KB |
testcase_37 | AC | 1 ms
5,248 KB |
testcase_38 | AC | 1 ms
5,248 KB |
testcase_39 | AC | 2 ms
5,248 KB |
ソースコード
#include <algorithm> #include <cmath> #include <iomanip> #include <iostream> #include <limits> #include <map> #include <queue> #include <set> #include <tuple> #include <vector> using namespace std; #define rep(i, n) for (int64_t i = 0; i < (n); i++) #define irep(i, n) for (int64_t i = 0; i <= (n); i++) #define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--) #define rirep(i, n) for (int64_t i = n; i >= 0; i--) struct Edge { int from; int to; int64_t capacity; int64_t flow; }; void maxflow(const vector<vector<int>> &outEdge, const vector<vector<int>> &inEdge, vector<Edge> &edgeData, const int source, const int sink) { const int n = outEdge.size(); const int m = edgeData.size(); while (true) { // check if reachable to sink vector<int> parent(n, -1); queue<int> q; q.push(source); while (!q.empty()) { int v = q.front(); q.pop(); for (const int e : outEdge[v]) { const Edge &data = edgeData[e]; const int nv = data.to; if (parent[nv] < 0 && data.capacity - data.flow > 0) { q.push(nv); parent[nv] = e; } } for (const int e : inEdge[v]) { const Edge &data = edgeData[e]; const int nv = data.from; if (parent[nv] < 0 && data.flow > 0) { q.push(nv); parent[nv] = e; } } } if (parent[sink] < 0) { break; } // select path from source to sink int64_t d = 1'000'000'000; int v = sink; while (v != source) { const int e = parent[v]; const Edge &data = edgeData[e]; if (data.to == v) { d = min(d, data.capacity - data.flow); v = data.from; } else { d = min(d, data.flow); v = data.to; } } // update flow on the path v = sink; while (v != source) { const int e = parent[v]; Edge &data = edgeData[e]; if (data.to == v) { data.flow += d; v = data.from; } else { data.flow -= d; v = data.to; } } } } int main() { int N, M, d; cin >> N >> M >> d; using Plane = tuple<int, int, int, int, int>; const int TMAX = 1'000'000'000; const int64_t INF = 1'000L * 1'000'000'000; vector<Plane> planes(M); vector<vector<int>> departures(N); rep(i, M) { int u, v, p, q, w; cin >> u >> v >> p >> q >> w; u--; v--; planes[i] = Plane(u, v, p, q + d, w); departures[u].push_back(p); } departures[0].push_back(0); departures[N - 1].push_back(TMAX + d); rep(i, N) { sort(departures[i].begin(), departures[i].end()); departures[i].erase(unique(departures[i].begin(), departures[i].end()), departures[i].end()); } int nodeNum = 0; vector<vector<int>> ids(N); rep(i, N) { for (const int d : departures[i]) { ids[i].push_back(nodeNum); nodeNum++; } } vector<vector<int>> outEdge(nodeNum), inEdge(nodeNum); vector<Edge> edgeData; int edgeNum = 0; // edges representing moving by plane rep(i, M) { int u, v, p, q, w; tie(u, v, p, q, w) = planes[i]; auto fromAddr = lower_bound(departures[u].begin(), departures[u].end(), p); auto toAddr = lower_bound(departures[v].begin(), departures[v].end(), q); if (toAddr != departures[v].end()) { int fromId = ids[u][fromAddr - departures[u].begin()]; int toId = ids[v].at(toAddr - departures[v].begin()); outEdge[fromId].push_back(edgeNum); inEdge[toId].push_back(edgeNum); Edge eData; eData.from = fromId; eData.to = toId; eData.flow = 0; eData.capacity = w; edgeData.push_back(eData); edgeNum++; } } cerr << "------------------------------" << endl; for (const Edge &data : edgeData) { cerr << data.from << " " << data.to << "\t" << data.flow << " / " << data.capacity << endl; } cerr << "------------------------------" << endl; // edges representing staying in a city rep(i, N) { const int tNum = departures[i].size(); rep(j, tNum - 1) { int fromId = ids[i][j]; int toId = ids[i][j + 1]; outEdge[fromId].push_back(edgeNum); inEdge[toId].push_back(edgeNum); Edge eData; eData.from = fromId; eData.to = toId; eData.flow = 0; eData.capacity = INF; edgeData.push_back(eData); edgeNum++; } } const int source = 0; const int sink = nodeNum - 1; maxflow(outEdge, inEdge, edgeData, source, sink); int64_t result = 0; for (const int e : inEdge[sink]) { result += edgeData[e].flow; } cout << result << endl; return 0; }