結果
問題 |
No.2325 Skill Tree
|
ユーザー |
![]() |
提出日時 | 2023-05-28 14:54:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,921 bytes |
コンパイル時間 | 2,115 ms |
コンパイル使用メモリ | 212,036 KB |
最終ジャッジ日時 | 2025-02-13 12:14:39 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 11 WA * 25 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, n) for (int i = 0; i < n; i++) #define INF (1LL << 60) #define all(v) (v).begin(), (v).end() template <class T> void chmin(T &a, T b) { if (a > b) a = b; } template <class T> void chmax(T &a, T b) { if (a < b) a = b; } int main() { ll N; cin >> N; vector<ll> L(N), A(N); rep(i, N - 1) { cin >> L[i + 1] >> A[i + 1]; A[i + 1]--; } ll Q; cin >> Q; vector<ll> l(N); rep(i, N) { l[i] = L[i]; } sort(all(l)); l.erase(unique(all(l)), l.end()); map<ll, ll> comp, rev; rep(i, l.size()) { comp[l[i]] = i; rev[i] = l[i]; } rep(i, N) { L[i] = comp[L[i]]; } vector<vector<ll>> level_to_idx(l.size()), A_to_idx(N); rep(i, N) { level_to_idx[L[i]].push_back(i); A_to_idx[A[i]].push_back(i); } vector<ll> ans(l.size()); vector<ll> ans2(N, -1); vector<ll> used(N); ll t = 1; ans[0] = 1; used[0] = 1; rep(i, l.size()) { if (i == 0) continue; rep(j, level_to_idx[i].size()) { ll idx = level_to_idx[i][j]; if (used[idx] == 1) continue; if (used[A[idx]] == 0) continue; used[idx] = 1; ans2[idx] = rev[i]; t++; rep(k, A_to_idx[A[i]].size()) { ll jdx = A_to_idx[A[i]][k]; if (used[jdx]) continue; if (L[jdx] > i) continue; used[jdx] = 1; ans2[jdx] = rev[i]; t++; } } ans[i] = t; } rep(i, Q) { ll t, x; cin >> t >> x; if (t == 1) { auto itr = upper_bound(all(l), x); --itr; cout << ans[distance(l.begin(), itr)] << endl; } else { x--; cout << ans2[x] << endl; } } }