結果
問題 | No.2325 Skill Tree |
ユーザー |
|
提出日時 | 2023-05-28 15:59:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,296 bytes |
コンパイル時間 | 2,369 ms |
コンパイル使用メモリ | 210,464 KB |
最終ジャッジ日時 | 2025-02-13 14:56:40 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 RE * 1 |
other | AC * 3 WA * 1 RE * 17 TLE * 15 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define fi first #define se second int dfs(vector<vector<int>> &g, vector<bool> &seen, vector<int> &l, int v){ seen[v] = true; int res = l[v]; for(int nv : g[v]){ if(!seen[nv]) res = max(res, dfs(g, seen, l, nv)); else res = (int)2e9; } return res; } int main(){ int n; cin >> n; vector<int> l(n); l[0] = 0; vector<vector<int>> g(n); for(int i = 1; i < n; i++){ cin >> l[i]; int a; cin >> a; g[i].push_back(a - 1); } vector<int> lmax(n, -1); lmax[0] = 1; vector<bool> seen(n, false); for(int i = 1; i < n; i++){ seen.assign(n, false); lmax[i] = dfs(g, seen, l, i); } map<int, int> level; for(int i = 0; i < n; i++) level[lmax[i]]++; int maxlevel = 1; for(int i = 0; i < n; i++){ maxlevel = max(maxlevel, lmax[i]); } vector<int> kinds(maxlevel + 1); kinds[1] = 1; for(int i = 2; i <= maxlevel; i++){ kinds[i] = kinds[i - 1] + level[i]; } int q; cin >> q; while(q--){ int k, xy; cin >> k >> xy; if(k == 1) cout << kinds[xy] << endl; if(k == 2) cout << lmax[xy - 1] << endl; } return 0; }