結果
問題 | No.2288 Somen Sliders |
ユーザー |
![]() |
提出日時 | 2023-04-28 22:57:49 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 38 ms / 2,000 ms |
コード長 | 1,848 bytes |
コンパイル時間 | 1,098 ms |
コンパイル使用メモリ | 97,552 KB |
実行使用メモリ | 10,240 KB |
最終ジャッジ日時 | 2024-11-17 21:54:43 |
合計ジャッジ時間 | 2,531 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
#include <iostream> #include <numeric> #include <vector> using namespace std; int main() { cin.tie(nullptr), ios::sync_with_stdio(false); int N, X, Y; cin >> N >> X >> Y; vector<vector<int>> P(X), Q(Y); for (auto &vec : P) { int len; cin >> len; vec.resize(len + 1); for (auto &x: vec) cin >> x, --x; vec.pop_back(); vec.erase(vec.begin()); } for (auto &vec : Q) { int len; cin >> len; vec.resize(len + 1); for (auto &x : vec) cin >> x, --x; vec.pop_back(); vec.erase(vec.begin()); } vector<int> belong_to(N, -1), pos(N, -1); for (int x = 0; x < X; ++x) { const auto &seq = P.at(x); for (int d = 0; d < int(seq.size()); ++d) { belong_to.at(seq.at(d)) = x; pos.at(seq.at(d)) = d; } } vector<int> next_red(N, -1); vector<int> pending; for (const auto &seq : Q) { int pr = -1; for (int x : seq) { if (belong_to.at(x) >= 0) next_red.at(x) = pr, pr = x; } if (pr >= 0) pending.push_back(pr); } vector<int> heights; for (const auto &v : P) heights.push_back(v.size()); while (pending.size()) { int now = pending.back(); pending.pop_back(); if (const int l = belong_to.at(now), p = pos.at(now); heights.at(l) > p) { if (heights.at(l) < int(P.at(l).size())) { int old = P.at(l).at(heights.at(l)); int pr = next_red.at(old); if (pr >= 0) pending.push_back(pr); } heights.at(l) = p; } else { int pr = next_red.at(now); if (pr >= 0) pending.push_back(pr); } } cout << accumulate(heights.cbegin(), heights.cend(), X) << endl; }