結果
問題 | No.2325 Skill Tree |
ユーザー |
![]() |
提出日時 | 2023-05-28 14:33:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 147 ms / 3,000 ms |
コード長 | 1,589 bytes |
コンパイル時間 | 1,179 ms |
コンパイル使用メモリ | 109,272 KB |
最終ジャッジ日時 | 2025-02-13 11:43:17 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include <iostream> #include <vector> #include <map> #include <iterator> #include <functional> #include <optional> struct Data { int L, A; }; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int N; std::cin >> N; auto G = std::vector<Data>(N + 1); for (int i = 2; i <= N; ++i) std::cin >> G[i].L >> G[i].A; std::map<int, int> _x; // レベルi になって覚えられる技の種類 auto y = std::vector(N + 1, std::optional<int>()); // 技i を覚えられるレベルの最小値 _x[0] = 1; y[1] = 0; auto cycle = std::vector(N + 1, false); std::function<int(int)> f = [&](const int i) { // 技i を覚えられるレベルの最小値 if (y[i]) return *y[i]; if (cycle[i]) return *(y[i] = -1); cycle[i] = true; int level = f(G[i].A); if (level < 0) return *(y[i] = -1); if (level < G[i].L) level = G[i].L; ++_x[level]; return *(y[i] = level); }; for (int i = 2; i <= N; ++i) f(i); std::map<int, int> x = _x; // レベルi までに覚えられる技の種類 for (auto i = next(x.begin()); i != x.end(); ++i) i->second += prev(i)->second; int Q; std::cin >> Q; while (Q--) { int q, i; std::cin >> q >> i; switch (q) { case 1: std::cout << prev(x.upper_bound(i))->second << "\n"; break; case 2: std::cout << *y[i] << "\n"; break; } } }