結果
問題 | No.2325 Skill Tree |
ユーザー |
![]() |
提出日時 | 2023-05-28 14:28:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 653 ms / 3,000 ms |
コード長 | 2,089 bytes |
コンパイル時間 | 2,449 ms |
コンパイル使用メモリ | 208,852 KB |
最終ジャッジ日時 | 2025-02-13 11:33:19 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> PP; //#define MOD 1000000007 #define MOD 998244353 #define INF 2305843009213693951 //#define INF 810114514 #define PI 3.141592653589 #define setdouble setprecision #define REP(i,n) for(ll i=0;i<(n);++i) #define OREP(i,n) for(ll i=1;i<=(n);++i) #define RREP(i,n) for(ll i=(n)-1;i>=0;--i) #define ALL(v) (v).begin(), (v).end() #define GOODBYE do { cout << "-1" << endl; return 0; } while (false) #define MM <<" "<< #define Endl endl #define debug true #define debug2 false vector<vector<ll>> G; vector<ll> L,A,S; /*void dfs(ll v,ll p){ S[v] = L[v]; for(ll e:G[v]){ S[v] = min(S[v],S[e]); } for(ll e:G[v]){ if(e==p)continue; dfs(e,v); } }*/ int main(void){ //cin.tie(nullptr); //ios::sync_with_stdio(false); ll N; cin >> N; L.resize(N); A.resize(N); L[0] = -1;A[0] = -1; REP(i,N){ if(i==0)continue; cin >> L[i] >> A[i]; A[i]--; } ll Q; cin >> Q; G.clear(); G.resize(N); REP(i,N){ if(i==0)continue; G[A[i]].push_back(i); //G[i].push_back(A[i]); } S.resize(N); REP(i,N){S[i] = INF;} //dfs(0,-1); priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> que; que.push({0,0}); //コスト、頂点番号 while(!que.empty()){ pair<ll,ll> q = que.top(); que.pop(); ll c = q.first, v = q.second; if(S[v]!=INF)continue; S[v] = c; for(ll e:G[v]){ if(S[e]!=INF)continue; que.push({max(c,L[e]),e}); } } /*REP(i,N){ cout << S[i] << " "; } cout << endl;*/ vector<ll> R = S; sort(ALL(R)); REP(_,Q){ ll t,x; cin >> t >> x; if(t==1){ auto it = upper_bound(ALL(R),x); cout << distance(R.begin(),it) << endl; }else{ ll s = S[x-1]; if(s==INF)s=-1; cout << s << endl; } } return 0; }