結果

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

ソースコード

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

#include <bits/stdc++.h>
#define mrep(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define rep(i, n) mrep(i, 0, n)
using namespace std;
using ll = long long;
const ll INF = ll(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;
unordered_map<ll, ll> memo0, memo1;
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) {
ll 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 (ll i = 0; i<N; i++) {
ll lvl = level_sorted[i];
ll ans = 0;
queue<ll> q;
q.push(1);
while(!q.empty()) {
ans++;
ll 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);
ll Q;
cin >> Q;
rep(_, Q) {
ll op, val;
cin >> op >> val;
if (op == 1) {
if (memo0.count(val)) {
cout << memo0[val] << "\n";
continue;
}
auto it = lower_bound(memo_L.begin(), memo_L.end(), ll(val));
if (*it != val) {it--;}
ll idx = it-memo_L.begin();
memo0[val] = memo_A[idx] - 1;
cout << memo_A[idx]-1 << "\n";
} else {
if (memo1.count(val)) {
cout << memo1[val] << "\n";
continue;
}
bool ac = false;
vector<bool> pushed(N+2, false);
pushed[val] = true;
ll ans = -1;
queue<ll> q;
q.push(val);
while(!q.empty()) {
ll s = q.front(); q.pop();
if (s == 1) {ac = true; break;}
for(auto ul: graph_rev[s]) {
auto [u, l] = ul;
if (pushed[u]) {continue;}
ans = max(ans, l);
if(l) {q.push(u); pushed[u] = true;}
}
}
if (!ac) {ans = -1;}
memo1[val] = ans;
cout << ans << "\n";
}
}
cout << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0