結果

問題 No.2325 Skill Tree
ユーザー みどみど
提出日時 2023-05-28 15:46:23
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,398 bytes
コンパイル時間 2,473 ms
コンパイル使用メモリ 213,308 KB
最終ジャッジ日時 2025-02-13 13:57:06
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 18 TLE * 18
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
#define mrep(i, s, n) for (int i = (s); i < (int)(n); i++)
#define rep(i, n) mrep(i, 0, n)
using namespace std;
using ll = long long;
const int INF = int(1e+9)+1;
const ll INFL = ll(1e+18)+1;
ll N;
vector<ll> L, A;
vector<vector<pair<ll,ll>>> graph, graph_rev;
vector<ll> memo_L, memo_A;
int main() {
cin >> N;
L.resize(N+2, 0), A.resize(N+2, 1);
rep(i, N-1) {cin >> L[i+2] >> A[i+2];}
graph = vector<vector<pair<ll, ll>>>(N+2);
graph_rev = vector<vector<pair<ll, ll>>>(N+2);
rep(i, N) {
int u = i+2, v = A[i+2];
graph[v].push_back(make_pair(u, L[i+2]));
graph_rev[u].push_back(make_pair(v, L[i+2]));
}
vector<ll> level_sorted(N);
copy(L.begin()+2, L.end(), level_sorted.begin());
sort(level_sorted.begin(), level_sorted.end());
memo_L.resize(N, 0);
memo_A.resize(N, 0);
for (int i = 0; i<N; i++) {
ll lvl = level_sorted[i];
int ans = 0;
queue<ll> q;
q.push(1);
while(!q.empty()) {
ans++;
int s = q.front(); q.pop();
//
for (auto un: graph[s]) {
auto [u, l] = un;
if (lvl < l) {continue;} //
q.push(u);
}
}
memo_L[i] = lvl;
memo_A[i] = ans;
}
memo_L.push_back(INFL);
int Q;
cin >> Q;
rep(_, Q) {
int op, val;
cin >> op >> val;
if (op == 1) {
auto it = lower_bound(memo_L.begin(), memo_L.end(), ll(val));
if (*it != val) {it--;}
int idx = it-memo_L.begin();
cout << memo_A[idx]-1 << endl;
} else {
bool ac = false;
vector<bool> done(N+2, false);
ll ans = -1;
queue<ll> q;
q.push(val);
while(!q.empty()) {
int s = q.front(); q.pop();
if (done[s]) {continue;}
done[s] = true;
if (s == 1) {ac = true; break;}
for(auto ul: graph_rev[s]) {
auto [u, l] = ul;
if (done[u]) {continue;}
ans = max(ans, l);
q.push(u);
}
}
if (!ac) {ans = -1;}
cout << ans << endl;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0