結果
問題 | No.654 Air E869120 |
ユーザー | テナガザル |
提出日時 | 2024-04-04 16:00:37 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 17 ms / 2,000 ms |
コード長 | 2,998 bytes |
コンパイル時間 | 1,411 ms |
コンパイル使用メモリ | 99,936 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-01 00:25:31 |
合計ジャッジ時間 | 2,694 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,816 KB |
testcase_03 | AC | 2 ms
6,816 KB |
testcase_04 | AC | 2 ms
6,820 KB |
testcase_05 | AC | 2 ms
6,816 KB |
testcase_06 | AC | 2 ms
6,816 KB |
testcase_07 | AC | 2 ms
6,820 KB |
testcase_08 | AC | 2 ms
6,820 KB |
testcase_09 | AC | 1 ms
6,820 KB |
testcase_10 | AC | 17 ms
6,816 KB |
testcase_11 | AC | 13 ms
6,816 KB |
testcase_12 | AC | 14 ms
6,816 KB |
testcase_13 | AC | 17 ms
6,816 KB |
testcase_14 | AC | 13 ms
6,816 KB |
testcase_15 | AC | 12 ms
6,816 KB |
testcase_16 | AC | 13 ms
6,816 KB |
testcase_17 | AC | 14 ms
6,820 KB |
testcase_18 | AC | 13 ms
6,820 KB |
testcase_19 | AC | 13 ms
6,820 KB |
testcase_20 | AC | 6 ms
6,816 KB |
testcase_21 | AC | 7 ms
6,820 KB |
testcase_22 | AC | 4 ms
6,820 KB |
testcase_23 | AC | 5 ms
6,816 KB |
testcase_24 | AC | 6 ms
6,816 KB |
testcase_25 | AC | 4 ms
6,820 KB |
testcase_26 | AC | 5 ms
6,816 KB |
testcase_27 | AC | 4 ms
6,820 KB |
testcase_28 | AC | 4 ms
6,816 KB |
testcase_29 | AC | 4 ms
6,816 KB |
testcase_30 | AC | 4 ms
6,816 KB |
testcase_31 | AC | 4 ms
6,820 KB |
testcase_32 | AC | 4 ms
6,820 KB |
testcase_33 | AC | 4 ms
6,816 KB |
testcase_34 | AC | 4 ms
6,820 KB |
testcase_35 | AC | 2 ms
6,816 KB |
testcase_36 | AC | 2 ms
6,820 KB |
testcase_37 | AC | 2 ms
6,820 KB |
testcase_38 | AC | 2 ms
6,816 KB |
testcase_39 | AC | 2 ms
6,820 KB |
コンパイルメッセージ
main.cpp: In instantiation of 'void maxflow<T>::add(int, int, T) [with T = long long int]': main.cpp:119:84: required from here main.cpp:17:33: warning: narrowing conversion of '(&((maxflow<long long int>*)this)->maxflow<long long int>::g.std::vector<std::vector<maxflow<long long int>::edge, std::allocator<maxflow<long long int>::edge> >, std::allocator<std::vector<maxflow<long long int>::edge, std::allocator<maxflow<long long int>::edge> > > >::operator[](((std::vector<std::vector<maxflow<long long int>::edge, std::allocator<maxflow<long long int>::edge> >, std::allocator<std::vector<maxflow<long long int>::edge, std::allocator<maxflow<long long int>::edge> > > >::size_type)t)))->std::vector<maxflow<long long int>::edge, std::allocator<maxflow<long long int>::edge> >::size()' from 'std::vector<maxflow<long long int>::edge, std::allocator<maxflow<long long int>::edge> >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing] 17 | g[s].push_back({t, g[t].size(), f}); | ~~~~~~~~~^~ main.cpp:18:36: warning: narrowing conversion of '((&((maxflow<long long int>*)this)->maxflow<long long int>::g.std::vector<std::vector<maxflow<long long int>::edge, std::allocator<maxflow<long long int>::edge> >, std::allocator<std::vector<maxflow<long long int>::edge, std::allocator<maxflow<long long int>::edge> > > >::operator[](((std::vector<std::vector<maxflow<long long int>::edge, std::allocator<maxflow<long long int>::edge> >, std::allocator<std::vector<maxflow<long long int>::edge, std::allocator<maxflow<long long int>::edge> > > >::size_type)s)))->std::vector<maxflow<long long int>::edge, std::allocator<maxflow<long long int>::edge> >::size() - 1)' from 'std::vector<maxflow<long long int>::edge, std::allocator<maxflow<long long int>::edge> >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing] 18 | g[t].push_back({s, g[s].size() - 1, 0}); | ~~~~~~~~~~~~^~~
ソースコード
#include <iostream> #include <algorithm> #include <stack> #include <queue> #include <vector> template<typename T> class maxflow { struct edge {int to, rep; T cap;}; std::vector<std::vector<edge>> g; std::vector<int> dis, id; public: maxflow(int n) : g(n), id(n), dis(n) {} void add(int s, int t, T f) { g[s].push_back({t, g[t].size(), f}); g[t].push_back({s, g[s].size() - 1, 0}); } T flow(int s, int t) { T ret = 0; while (true) { bfs(s); if (dis[t] <= dis[s]) return ret; id.assign(id.size(), 0); T val; while ((val = path(s, t)) > 0) ret += val; } } private: void bfs(int s) { dis.assign(g.size(), -1); dis[s] = 0; std::queue<int> q; for (q.push(s); !q.empty(); q.pop()) { int now = q.front(); for (auto &v : g[now]) { if (v.cap > 0 && dis[v.to] < 0) { dis[v.to] = dis[now] + 1; q.push(v.to); } } } } T path(int s, int t) { const T inf = ((1LL << 60) | (1 << 30)); std::stack<edge> st; T ret = inf; st.push({s, -1, inf}); while (!st.empty()) { auto now = st.top(); st.pop(); if (now.rep == -1) { if (now.to == t) { ret = now.cap; break; } for (int &i = id[now.to]; i < g[now.to].size(); ++i) { auto &e = g[now.to][i]; if (dis[e.to] > dis[now.to] && e.cap > 0) { st.push({e.to, e.rep, 0}); st.push({e.to, -1, std::min(e.cap, now.cap)}); } } } } if (ret == inf) return 0; int now = t; while (now != s) { while (!st.empty() && st.top().to != now) st.pop(); edge &v1 = st.top(), &v2 = g[v1.to][v1.rep]; v2.cap += ret; g[v2.to][v2.rep].cap -= ret; now = v2.to; } return ret; } }; using namespace std; int main() { const long long inf = 1LL << 60; int n, m, d; cin >> n >> m >> d; vector<int> u(m), v(m), p(m), q(m), w(m); vector<vector<int>> t(n); for (int i = 0; i < m; ++i) { cin >> u[i] >> v[i] >> p[i] >> q[i] >> w[i]; --u[i], --v[i]; t[u[i]].push_back(p[i]); t[v[i]].push_back(q[i] + d); } t[0].push_back(0); t[n - 1].push_back(2e9); for (int i = 0; i < n; ++i) { sort(t[i].begin(), t[i].end()); t[i].erase(unique(t[i].begin(), t[i].end()), t[i].end()); } vector<int> id(n + 1); for (int i = 1; i <= n; ++i) id[i] = id[i - 1] + t[i - 1].size(); maxflow<long long> mf(id[n]); for (int i = 0; i < n; ++i) for (int j = 0; j < (int)t[i].size() - 1; ++j) mf.add(id[i] + j, id[i] + j + 1, inf); for (int i = 0; i < m; ++i) { int id1 = lower_bound(t[u[i]].begin(), t[u[i]].end(), p[i]) - t[u[i]].begin(); int id2 = lower_bound(t[v[i]].begin(), t[v[i]].end(), q[i] + d) - t[v[i]].begin(); mf.add(id[u[i]] + id1, id[v[i]] + id2, w[i]); } long long ans = mf.flow(0, id[n] - 1); cout << ans << endl; }