結果
問題 |
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 998244353 const 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; } } }