結果
問題 | No.2325 Skill Tree |
ユーザー |
|
提出日時 | 2023-04-15 11:35:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 400 ms / 3,000 ms |
コード長 | 1,202 bytes |
コンパイル時間 | 2,371 ms |
コンパイル使用メモリ | 205,900 KB |
最終ジャッジ日時 | 2025-02-12 08:46:56 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>using namespace std;const int INF = 1 << 30;vector<int> l;vector<vector<int>> G;vector<int> ans1;void dfs(int curr, int prev){for(auto x : G[curr]){if(x == prev){continue;}ans1[x] = max(ans1[curr], l[x]);dfs(x, curr);}}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n; cin >> n;G.resize(n);l.resize(n);ans1.assign(n, -1);vector<tuple<int, int, int>> skill(n - 1);for(int i = 1; i < n; i++){int a; cin >> l[i] >> a; a--;G[i].push_back(a);G[a].push_back(i);}ans1[0] = 1;dfs(0, -1);vector<int> ans2;for(int i = 0; i < n; i++){if(ans1[i] != -1){ans2.emplace_back(ans1[i]);}}sort(ans2.begin(), ans2.end());int q; cin >> q;while(q--){int t; cin >> t;if(t == 1){int x; cin >> x;auto iter = upper_bound(ans2.begin(), ans2.end(), x);int k = iter - ans2.begin();cout << k << endl;}else{int y; cin >> y; y--;cout << ans1[y] << endl;}}}