結果
問題 | No.2325 Skill Tree |
ユーザー |
|
提出日時 | 2023-05-28 15:42:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 615 ms / 3,000 ms |
コード長 | 2,550 bytes |
コンパイル時間 | 2,215 ms |
コンパイル使用メモリ | 208,632 KB |
最終ジャッジ日時 | 2025-02-13 13:47:41 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef long double ld;typedef pair<ll, ll> pll;const ll LongINF=1000000000000000000;const int INF=1000000007;const int dx[]={0,1,0,-1};const int dy[]={1,0,-1,0};template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}template <class T, class Y>T GCD(T a, Y b){if(a<b){T c=a;a=b;b=c;}if (a % b == 0){return b;}return GCD(b, a % b);}template<class T,class Y>T LCM(T a,Y b){return (a*b)/GCD(a,b);}void clear(queue<pair<int, int>> &q){queue<pair<int, int>> empty;swap(q, empty);} //queueの中身の型は適時変更を忘れないusing vi=vector<int>;using vii=vector<vi>;#define REP(i,a,b) for(ll i=(a);i<(b);i++)#define rep(i,n) REP(i,0,n)#define pb push_back#define rv reverse#define ALL(a) (a).begin(),(a).end()#define decimal(x) fixed<<setprecision(x)int main(){int N;cin>>N;vi vertex(N+1,-1);vector<pair<int,int>> skills(N+1);vii graph(N+1);REP(i,2,N+1){int l,a;cin>>l>>a;skills[i]={l,a};}REP(i,2,N+1){graph[skills[i].second].pb(i);}queue<pair<int,int>>que;que.push({1,1});while(!que.empty()){auto [x,level]=que.front();que.pop();for(auto y:graph[x]){if(vertex[y]!=-1)continue;vertex[y]=max(level,skills[y].first);que.push({y,vertex[y]});}}vi sortedSkills;sortedSkills.pb(1);rep(i,N+1){if(vertex[i]>0)sortedSkills.pb(vertex[i]);}sort(ALL(sortedSkills));int Q;cin>>Q;rep(q,Q){int p;cin>>p;if(p==1){int x;cin>>x;cout<<upper_bound(ALL(sortedSkills),x)-sortedSkills.begin()<<endl;}else{int y;cin>>y;cout<<vertex[y]<<endl;}}return 0;}/*クエリ系は前処理がいる。累積和かなあ二分探索が使えそうsortして、要求レベルが低い技ごとに考えていく?<-だめlevelに書く技の要求レベルを持たせる。技の習得を待つ必要があるときはどうしたら良いんだ技を深掘りしていく。その技自体を覚えるレベルと、必要な技のレベルから決めていく?通っていったところをqueで管理して、レベルを反映させてく?力技でいける?*/