結果
問題 | No.2325 Skill Tree |
ユーザー |
![]() |
提出日時 | 2023-05-28 15:46:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,398 bytes |
コンパイル時間 | 2,473 ms |
コンパイル使用メモリ | 213,308 KB |
最終ジャッジ日時 | 2025-02-13 13:57:06 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 TLE * 18 |
ソースコード
#include <bits/stdc++.h>#define mrep(i, s, n) for (int i = (s); i < (int)(n); i++)#define rep(i, n) mrep(i, 0, n)using namespace std;using ll = long long;const int INF = int(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;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) {int 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 (int i = 0; i<N; i++) {ll lvl = level_sorted[i];int ans = 0;queue<ll> q;q.push(1);while(!q.empty()) {ans++;int 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);int Q;cin >> Q;rep(_, Q) {int op, val;cin >> op >> val;if (op == 1) {auto it = lower_bound(memo_L.begin(), memo_L.end(), ll(val));if (*it != val) {it--;}int idx = it-memo_L.begin();cout << memo_A[idx]-1 << endl;} else {bool ac = false;vector<bool> done(N+2, false);ll ans = -1;queue<ll> q;q.push(val);while(!q.empty()) {int s = q.front(); q.pop();if (done[s]) {continue;}done[s] = true;if (s == 1) {ac = true; break;}for(auto ul: graph_rev[s]) {auto [u, l] = ul;if (done[u]) {continue;}ans = max(ans, l);q.push(u);}}if (!ac) {ans = -1;}cout << ans << endl;}}}