結果
問題 | No.2325 Skill Tree |
ユーザー |
![]() |
提出日時 | 2023-05-28 15:46:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 397 ms / 3,000 ms |
コード長 | 1,999 bytes |
コンパイル時間 | 1,853 ms |
コンパイル使用メモリ | 180,812 KB |
実行使用メモリ | 9,856 KB |
最終ジャッジ日時 | 2024-12-27 08:36:46 |
合計ジャッジ時間 | 16,241 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
using namespace std;#include<bits/stdc++.h>void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); cout<<fixed<<setprecision(15);_main(); return 0;}#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")typedef long long ll;typedef long double ld;template<class ll> inline bool chmax(ll& a, ll b) { if (a < b) { a = b; return 1; } return 0; }template<class ll> inline bool chmin(ll& a, ll b) { if (a > b) { a = b; return 1; } return 0; }#define rep(i, star,fini) for (int i = star; i < fini; i++)#define ALL(x) std::begin(x), std::end(x)#define INF ((1LL<<62)-(1LL<<31))#define bit(x,i)(((x)>>(i))&1)long double distance(long double xi,long double yi,long double xj,long double yj){return sqrt(1.0*((xi-xj)*(xi-xj))+1.0*((yi-yj)*(yi-yj)));}vector<ll>needlv(200005,-1);ll l[200005],a[200005];void kakutei(ll pos){if(needlv[pos]==-2)return;if(needlv[pos]!=-1)return;if(needlv[a[pos]]>-1){needlv[pos]=max(l[pos],needlv[a[pos]]);}else{needlv[pos]=-2;kakutei(a[pos]);if(needlv[a[pos]]>-1){needlv[pos]=max(l[pos],needlv[a[pos]]);}}}void _main(){ll n;cin >> n;l[0]=0;a[0]=0;needlv[0]=0;rep(i,1,n){cin >> l[i] >> a[i];a[i]--;}rep(i,0,n){kakutei(i);}map<ll,ll>qone;for(ll i:needlv){if(i<0)continue;qone[i]++;}vector<ll>ans;vector<ll>ans_name;ll prev = 0;for(auto i:qone){ans_name.push_back(i.first);ans.push_back(prev+i.second);prev = ans.back();}ll q;cin >> q;while (q--){ll t,x;cin >> t;if(t==1){cin >> x;ll pos = upper_bound(ALL(ans_name),x)-ans_name.begin();pos--;cout<<ans[pos]<<endl;}else{cin >> x;cout<<(needlv[x-1]>0?needlv[x-1]:-1)<<endl;}}}