結果
問題 | No.2325 Skill Tree |
ユーザー |
|
提出日時 | 2023-05-28 15:45:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 605 ms / 3,000 ms |
コード長 | 2,104 bytes |
コンパイル時間 | 2,307 ms |
コンパイル使用メモリ | 178,476 KB |
実行使用メモリ | 6,616 KB |
最終ジャッジ日時 | 2024-12-27 08:31:41 |
合計ジャッジ時間 | 21,295 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
//MMA Contest 015 C#include<bits/stdc++.h>using namespace std;typedef int64_t ll;vector<int> L={0};vector<int> A={-1};vector<int> ReallyDemandedLevel;//-3:計算途中、-2:未計算、-1:不可能、非負整数:スライムがその技を覚えるために必要なレベルの最小値int f_ReallyDemandedLevel(int n){if(ReallyDemandedLevel.at(n)==-3)return -1;//閉路ReallyDemandedLevel.at(n)=-3;int previous_node=A.at(n);int &a=ReallyDemandedLevel.at(previous_node);if(a==-2)a=f_ReallyDemandedLevel(previous_node);if(a==-1 || a==-3)return -1;int b=L.at(n);return max(a,b);}//main関数ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーint main(){int n; cin>>n;for(int i=1;i<n;i++){int l,a; cin>>l>>a;L.push_back(l);A.push_back(a-1);}ReallyDemandedLevel.assign(n,-2);ReallyDemandedLevel.at(0)=0;for(int i=1;i<n;i++){if(ReallyDemandedLevel.at(i)==-2){ReallyDemandedLevel.at(i)=f_ReallyDemandedLevel(i);}}//for(int i=0;i<n;i++){// cout<<i<<' '<<ReallyDemandedLevel.at(i)<<endl;//}map<int,int>Mp;for(int l:ReallyDemandedLevel)if(l>=0)Mp[l]++;int sum=0;//クエリ1のためにMpを積分for(pair<int,int> p:Mp){sum+=p.second;Mp[p.first]=sum;}//for(pair<int,int> p:Mp)cout<<"Mp "<<p.first<<" "<<p.second<<endl;int q; cin>>q;//cout<<"q="<<q<<endl;while(q--){int query_type; cin>>query_type;if(query_type==1){//レベル x のスライムが覚えられる技の種類数の最大値を出力する。int x; cin>>x;auto itr=Mp.upper_bound(x);itr--;pair<int,int> p=*itr;cout<<p.second<<endl;}else{//スライムが技 y を覚えるために必要なレベルの最小値を出力する。技 y を覚えることができない場合には−1を出力する。int y; cin>>y;cout<<ReallyDemandedLevel.at(y-1)<<endl;}}return 0;}