結果
問題 | No.2325 Skill Tree |
ユーザー |
![]() |
提出日時 | 2023-05-28 15:09:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 670 ms / 3,000 ms |
コード長 | 1,672 bytes |
コンパイル時間 | 2,278 ms |
コンパイル使用メモリ | 214,980 KB |
最終ジャッジ日時 | 2025-02-13 12:37:54 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#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);vector<ll> l = {0};vector<vector<ll>> revA(N);rep(i, N - 1) {cin >> L[i + 1] >> A[i + 1];A[i + 1]--;l.push_back(L[i + 1]);revA[A[i + 1]].push_back(i + 1);}sort(all(l));l.erase(unique(all(l)), l.end());unordered_map<ll, ll> mp;vector<ll> rev(l.size());rep(i, l.size()) {mp[l[i]] = i;rev[i] = l[i];}rep(i, N) { L[i] = mp[L[i]]; }queue<ll> que;vector<ll> ans1(N), ans2(N, -1);ans2[0] = 1;rep(i, N) {if (A[i] == 0) que.push(i);}while (!que.empty()) {ll t = que.front();que.pop();if (ans2[t] != -1) continue;ans2[t] = max(ans2[A[t]], rev[L[t]]);rep(i, revA[t].size()) { que.push(revA[t][i]); }}// rep(i, N) { cout << ans2[i] << endl; }rep(i, N) {if (ans2[i] == -1) continue;ans1[mp[ans2[i]]]++;}rep(i, l.size() - 1) { ans1[i + 1] += ans1[i]; }ll Q;cin >> Q;rep(i, Q) {ll t, x;cin >> t >> x;if (t == 1) {auto itr = upper_bound(all(l), x);--itr;cout << ans1[distance(l.begin(), itr)] << endl;} else {x--;cout << ans2[x] << endl;}}}