結果
問題 | No.2325 Skill Tree |
ユーザー |
![]() |
提出日時 | 2023-05-28 16:49:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,750 bytes |
コンパイル時間 | 2,716 ms |
コンパイル使用メモリ | 218,756 KB |
最終ジャッジ日時 | 2025-02-13 15:30:09 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 2 |
other | WA * 18 TLE * 18 |
ソースコード
#include <bits/stdc++.h>#define mrep(i, s, n) for (ll i = (s); i < (ll)(n); i++)#define rep(i, n) mrep(i, 0, n)using namespace std;using ll = long long;const ll INF = ll(1e+9)+1;const ll INFL = ll(1e+18)+1;ll N;vector<ll> L, A;vector<vector<pair<ll,ll>>> graph, graph_rev;vector<ll> memo_L, memo_A;unordered_map<ll, ll> memo0, memo1;int main() {cin >> N;L.resize(N+2, 0), A.resize(N+2, 1);rep(i, N-1) {cin >> L[i+2] >> A[i+2];}graph = vector<vector<pair<ll, ll>>>(N+2);graph_rev = vector<vector<pair<ll, ll>>>(N+2);rep(i, N) {ll u = i+2, v = A[i+2];graph[v].push_back(make_pair(u, L[i+2]));graph_rev[u].push_back(make_pair(v, L[i+2]));}vector<ll> level_sorted(N);copy(L.begin()+2, L.end(), level_sorted.begin());sort(level_sorted.begin(), level_sorted.end());memo_L.resize(N, 0);memo_A.resize(N, 0);for (ll i = 0; i<N; i++) {ll lvl = level_sorted[i];ll ans = 0;queue<ll> q;q.push(1);while(!q.empty()) {ans++;ll s = q.front(); q.pop();// 隣接している頂点を追加for (auto un: graph[s]) {auto [u, l] = un;if (lvl < l) {continue;} // レベル不足q.push(u);}}memo_L[i] = lvl;memo_A[i] = ans;}memo_L.push_back(INFL);ll Q;cin >> Q;rep(_, Q) {ll op, val;cin >> op >> val;if (op == 1) {if (memo0.count(val)) {cout << memo0[val] << '\n';continue;}auto it = lower_bound(memo_L.begin(), memo_L.end(), ll(val));if (*it != val) {it--;}ll idx = it-memo_L.begin();memo0[val] = memo_A[idx] - 1;cout << memo_A[idx]-1 << '\n';} else {if (memo1.count(val)) {cout << memo1[val] << '\n';continue;}bool ac = false;vector<bool> pushed(N+2, false);pushed[val] = true;ll ans = -1;queue<ll> q;q.push(val);while(!q.empty()) {ll s = q.front(); q.pop();if (s == 1) {ac = true; break;}for(auto ul: graph_rev[s]) {auto [u, l] = ul;if (pushed[u]) {continue;}ans = max(ans, l);if(l) {q.push(u); pushed[u] = true;}}}if (!ac) {ans = -1;}memo1[val] = ans;cout << ans << '\n';}cout << endl;}}