結果
問題 | No.2325 Skill Tree |
ユーザー |
![]() |
提出日時 | 2023-05-28 14:26:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 604 ms / 3,000 ms |
コード長 | 2,240 bytes |
コンパイル時間 | 2,022 ms |
コンパイル使用メモリ | 205,712 KB |
最終ジャッジ日時 | 2025-02-13 11:28:53 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>#include <numeric>// #include <atcoder/modint>using namespace std;// using namespace atcoder;// using mint = modint998244353;#define i64 int_fast64_tconst i64 INF = INT64_MAX;const i64 ERR = INT64_MIN;const i64 MOD = 998244353;// 切り上げi64 ceil_devide(i64 x, i64 y) {return (x + y - 1) / y;}// 切り捨てi64 floor_devide(i64 x, i64 y) {return x / y;}i64 sum_linear(i64 n) {return n * (n+1) / 2;}vector<i64> need_level_raw;vector<i64> need_level;vector<i64> need_skill;vector<bool> done;i64 get_need_level(i64 i) {done.at(i) = true;if (need_level.at(i) == -1) {if (done.at(need_skill.at(i))) {need_level.at(i) = INF;} else {need_level.at(i) = max(need_level_raw.at(i), get_need_level(need_skill.at(i)));}}done.at(i) = false;return need_level.at(i);}int main(){i64 n;cin >> n;need_level_raw = vector<i64>(n);need_level = vector<i64>(n, -1);need_skill = vector<i64>(n);done = vector<bool>(n);need_level_raw.at(0) = 0;need_level.at(0) = 0;need_skill.at(0) = 0;for (size_t i = 1; i < n; i++){i64 L,A;cin >> L >> A;need_level_raw.at(i) = L;need_skill.at(i) = A-1;}map<i64,i64> level_num;for (size_t i = 0; i < n; i++){if (get_need_level(i) == INF) {continue;}level_num[get_need_level(i)]++;}i64 sum = 0;for (auto &&i : level_num){sum += i.second;i.second = sum;}i64 q;cin >> q;for (size_t i = 0; i < q; i++){i64 mode;cin >> mode;switch (mode){case 1:{i64 x;cin >> x;auto itr = level_num.upper_bound(x);itr--;cout << (*itr).second << endl;}break;case 2:{i64 y;cin >> y;i64 res= get_need_level(y-1);if (res == INF) {res = -1;}cout << res << endl;}break;}}return 0;}