結果

問題 No.2325 Skill Tree
ユーザー cho435
提出日時 2023-05-28 14:04:23
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 605 ms / 3,000 ms
コード長 848 bytes
コンパイル時間 2,052 ms
コンパイル使用メモリ 204,204 KB
最終ジャッジ日時 2025-02-13 10:45:47
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for (int i=0;i<(int)(n);i++)
int main(){
int n;
cin>>n;
vector<int> l(n,0),a(n,0);
rep(i,n-1) cin>>l.at(i+1)>>a.at(i+1);
rep(i,n) a.at(i)--;
vector<vector<int>> g(n);
rep(i,n-1){
g.at(a.at(i+1)).push_back(i+1);
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
pq.push({0,0});
vector<int> q1;
vector<int> q2(n,-1);
while(!pq.empty()){
auto [lv,nw]=pq.top();
pq.pop();
q2.at(nw)=lv;
q1.push_back(lv);
for(int nx:g.at(nw)){
pq.push({max(lv,l.at(nx)),nx});
}
}
int q;
cin>>q;
rep(Qi,q){
int t,x;
cin>>t>>x;
if(t==1){
int ans=upper_bound(q1.begin(),q1.end(),x)-q1.begin();
cout<<ans<<'\n';
}else{
cout<<q2.at(x-1)<<'\n';
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0