結果
問題 | No.1014 competitive fighting |
ユーザー | kibuna |
提出日時 | 2020-03-23 22:53:54 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,262 bytes |
コンパイル時間 | 3,712 ms |
コンパイル使用メモリ | 186,224 KB |
実行使用メモリ | 106,252 KB |
最終ジャッジ日時 | 2023-08-28 13:08:44 |
合計ジャッジ時間 | 24,781 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | AC | 67 ms
27,620 KB |
testcase_11 | AC | 99 ms
36,672 KB |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
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 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | AC | 22 ms
9,704 KB |
testcase_34 | AC | 429 ms
82,780 KB |
testcase_35 | AC | 596 ms
106,252 KB |
testcase_36 | AC | 363 ms
75,052 KB |
testcase_37 | AC | 8 ms
5,800 KB |
testcase_38 | AC | 326 ms
69,076 KB |
testcase_39 | AC | 137 ms
36,192 KB |
testcase_40 | AC | 314 ms
68,036 KB |
testcase_41 | AC | 200 ms
48,616 KB |
testcase_42 | AC | 549 ms
104,992 KB |
testcase_43 | AC | 19 ms
8,712 KB |
testcase_44 | AC | 481 ms
95,332 KB |
testcase_45 | AC | 264 ms
57,152 KB |
testcase_46 | AC | 36 ms
12,672 KB |
testcase_47 | AC | 135 ms
34,040 KB |
testcase_48 | AC | 397 ms
77,136 KB |
testcase_49 | AC | 11 ms
6,356 KB |
testcase_50 | AC | 539 ms
100,116 KB |
testcase_51 | AC | 275 ms
59,776 KB |
testcase_52 | AC | 12 ms
6,572 KB |
testcase_53 | WA | - |
ソースコード
#include <bits/stdc++.h> using namespace std; using lint = long long; const lint inf = 1LL << 60; const lint mod = 1000000007; struct StronglyConnectedComponents { vector<vector<int>> const &edges_in; vector<vector<int>> edges, rev, dag; vector<int> comp, order, used; vector<vector<int>> cs; // list of nodes in each component StronglyConnectedComponents(vector<vector<int>> const &g) : edges_in(g), edges(g.size()), rev(g.size()), comp(g.size(), -1), used(g.size()), cs(g.size()) { for (int i = 0; i < (int)edges_in.size(); ++i) { for (auto &v : edges_in[i]) { edges[i].push_back(v); rev[v].push_back(i); } } build(); } int operator[](int k) { return comp[k]; } void dfs(int c) { if (used[c]) return; used[c] = true; for (auto &v : edges[c]) dfs(v); order.push_back(c); } void rdfs(int c, int cnt) { if (comp[c] != -1) return; comp[c] = cnt; cs[cnt].emplace_back(c); for (auto &v : rev[c]) rdfs(v, cnt); } void build() { for (int i = 0; i < (int)edges.size(); ++i) dfs(i); reverse(order.begin(), order.end()); int ptr = 0; for (auto &i : order) { if (comp[i] == -1) rdfs(i, ptr++); } dag.resize(ptr); for (int i = 0; i < (int)edges_in.size(); ++i) { int x = comp[i]; for (auto &v : edges_in[i]) { int y = comp[v]; if (x == y) continue; dag[x].push_back(y); } } } }; template <class T> bool chmax(T &a, const T &b) { return (a < b) ? (a = b, 1) : 0; } template <class T> bool chmin(T &a, const T &b) { return (b < a) ? (a = b, 1) : 0; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); lint n; cin >> n; map<lint, lint> idx; vector<lint> a(n), b(n), c(n); for (int i = 0; i < n; ++i) { cin >> a[i] >> b[i] >> c[i]; idx[a[i]] = 0; idx[b[i] - c[i]] = 0; } int id = 0; for (auto &p : idx) { p.second = id++; } int k = idx.size(); vector<vector<int>> edges(n + k); for (int i = 0; i < k - 1; ++i) { edges[i].push_back(i + 1); } for (int i = k; i < k + n; ++i) { edges[i].push_back(idx[a[i - k]]); edges[idx[b[i - k] - c[i - k]]].push_back(i); } StronglyConnectedComponents scc(edges); vector<int> cnt(n + k, 0); for (int i = k; i < n + k; ++i) { cnt[scc[i]]++; } lint m = scc.dag.size(); vector<lint> dp(m, 0); for (int i = 0; i < m; ++i) { if (cnt[i] > 1) { dp[i] = inf; continue; } for (auto &v : scc.cs[i]) { if (v >= k) dp[i] += b[v - k]; } for (auto &v : scc.dag[i]) { chmax(dp[v], dp[i]); } } for (int i = k; i < k + n; ++i) { if (dp[scc[i]] >= inf) cout << "BAN" << "\n"; else cout << dp[scc[i]] << "\n"; } return 0; }