結果
問題 | No.2325 Skill Tree |
ユーザー |
|
提出日時 | 2023-05-28 14:50:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 501 ms / 3,000 ms |
コード長 | 1,115 bytes |
コンパイル時間 | 5,164 ms |
コンパイル使用メモリ | 254,976 KB |
最終ジャッジ日時 | 2025-02-13 12:06:46 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using ll = long long;#define MOD 1000000007#define Mod 998244353const int MAX = 1000000005;const long long INF = 1000000000000000005LL;using namespace std;using namespace atcoder;vector<int> need(200005, MAX), L(200005);void dfs(int v, int p, vector<vector<int>> &G, int mx = 1) {mx = max(mx, L[v]);need[v] = min(need[v], mx);for (int nv : G[v]) {if (nv == p) continue;dfs(nv, v, G, mx);}}int main() {ios::sync_with_stdio(0);cin.tie();int N;cin >> N;vector<vector<int>> G(N);L[0] = 1;for (int i = 1; i < N; i++) {int a;cin >> L[i] >> a; a--;G[a].push_back(i);}dfs(0, -1, G);int Q;cin >> Q;auto sorted = need;sort(sorted.begin(), sorted.end());while (Q--) {int t, x;cin >> t >> x;if (t == 1) {cout << upper_bound(sorted.begin(), sorted.end(), x) - sorted.begin() << endl;} else {x--;cout << (need[x] == MAX ? -1 : need[x]) << endl;}}}