結果

問題 No.2325 Skill Tree
ユーザー シアン
提出日時 2023-05-28 14:41:46
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,706 ms / 3,000 ms
コード長 1,483 bytes
コンパイル時間 17,330 ms
コンパイル使用メモリ 334,188 KB
最終ジャッジ日時 2025-02-13 11:55:22
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
const int INF = 1001001001;
const ll LINF = 1001001001001001001;
const ll MOD = 998244353;
// DFS
vector<bool> seen;
vector<int> level;
map<int,int> mp;
void dfs(const vector<vector<pair<int,int>>>& G, int V, int ma) {
seen.at(V) = true;
level.at(V) = ma;
mp[ma]++;
for (auto next : G.at(V)) {
if (seen.at(next.first)) continue;
dfs(G, next.first, max(ma,next.second));
}
}
//
int binarySearch(vector<pair<int,int>> Sorted,int K) {
int ok = -1;
int ng = Sorted.size();
while(abs(ok-ng)>1) {
int mid = (ok+ng)/2;
bool flg = Sorted.at(mid).first<=K;
if(flg) ok=mid;
else ng=mid;
}
return ok;
}
int main() {
int n;cin>>n;
seen.resize(n);
level.resize(n);
for(int i=0;i<n;i++) level.at(i)=-2;
level.at(0)=0;
vector t(n, vector<pair<int,int>>());
for(int i=1;i<n;i++) {
int l,a;cin>>l>>a;
a--;l--;
t.at(a).push_back(make_pair(i,l));
}
dfs(t,0,0);
vector<pair<int,int>> kind;
for(auto ele : mp) {
kind.push_back(ele);
}
sort(kind.begin(),kind.end());
for(int i=1;i<kind.size();i++) {
kind.at(i).second += kind.at(i-1).second;
}
int Q;cin>>Q;
while(Q--) {
int q,x;cin>>q>>x;x--;
if(q==1) {
int idx = binarySearch(kind, x);
cout << kind.at(idx).second << endl;
} else {
cout << level.at(x)+1 << endl;
}
}
exit(0);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0