結果

問題 No.2325 Skill Tree
ユーザー Pres1dentPres1dent
提出日時 2023-05-28 14:58:27
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 526 ms / 3,000 ms
コード長 15,134 bytes
コンパイル時間 5,085 ms
コンパイル使用メモリ 279,380 KB
最終ジャッジ日時 2025-02-13 12:20:15
ジャッジサーバーID
(参考情報)
judge5 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

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

#include "bits/stdc++.h"
#include <unistd.h>
using namespace std;
#include "atcoder/all"
using namespace atcoder;
using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using i_i = pair<int, int>;
using l_l = pair<i64, i64>;
using d_d = pair<double, double>;
using s_s = pair<string, string>;
using i_i_i = tuple<int, int, int>;
using i_i_i_i = tuple<int, int, int, int>;
using l_l_l = tuple<i64, i64, i64>;
using l_l_l_l = tuple<i64, i64, i64, i64>;
using _bool = int;
#define rep(i, n) for(i64 i = 0; i < n; i++)
#define rep2(i, l, r) for(i64 i = l; i < r; i++)
#define rrep(i, n) for(i64 i = n - 1; i >= 0; i--)
#define rrep2(i, l, r) for(i64 i = r - 1; i >= l; i--)
#define ifbit(n,k) ((n>>k)&1) //if kth bit of n is on then true (sitakara, 0-indexed)
#define zpad(i) cout << setfill('0') << setw(i)
#define dout cout << fixed << setprecision(10)
#define douts(i) cout << fixed << setprecision(i) << scientific
#define pcnt __builtin_popcount
constexpr int INF = 2147483647;
constexpr i64 I64F = 9223372036854775807;
template <class T> bool chmax(T &l, const T &r) { if (l < r) { l = r; return true; } return false; }
template <class T> bool chmin(T &l, const T &r) { if (l > r) { l = r; return true; } return false; }
template <class T> pair<int, bool> ub(const vector<T> &v, const T &key) { int ind = upper_bound(v.begin(), v.end(), key) - v.begin(); if (ind == (int
    )v.size()) return make_pair(0, false); return make_pair(ind, true); }
template <class T> pair<int, bool> rub(const vector<T> &v, const T &key) { int ind = upper_bound(v.rbegin(), v.rend(), key, [](const T & l, const T &
    r) { return l > r; }) - v.rbegin(); if (ind == (int)v.size()) return make_pair(0, false); return make_pair((int)v.size() - 1 - ind, true); }
template <class T> pair<int, bool> lb(const vector<T> &v, const T &key) { int ind = lower_bound(v.begin(), v.end(), key) - v.begin(); if (ind == (int
    )v.size()) return make_pair(0, false); return make_pair(ind, true); }
template <class T> pair<int, bool> rlb(const vector<T> &v, const T &key) { int ind = lower_bound(v.rbegin(), v.rend(), key, [](const T & l, const T &
    r) { return l > r; }) - v.rbegin(); if (ind == (int)v.size()) return make_pair(0, false); return make_pair((int)v.size() - 1 - ind, true); }
void pu(vector<vector<char>> v) { for (int i = 0; i < v.size(); i++) { for (int j = 0; j < v[i].size(); j++) { cout << v[i][j]; } cout << endl; } }
i64 max(i64 l, int r) { return max(l, (i64)r); }
i64 max(int l, i64 r) { return max((i64)l, r); }
void pu(int v) { cout << v << endl; }
void pu(i64 v) { cout << v << endl; }
void pu(double v) { cout << fixed << setprecision(14) << v << endl; }
void pu(ld v) { cout << fixed << setprecision(14) << v << endl; }
void pu(string v) { cout << v << endl; }
void pu(modint998244353 v) { cout << v.val() << endl; }
void pu(modint1000000007 v) { cout << v.val() << endl; }
void pu(vector<int> v) { rep(i, v.size()) cout << v[i] << (i + 1 == v.size() ? "\n" : " "); }
void pu(vector<i64> v) { rep(i, v.size()) cout << v[i] << (i + 1 == v.size() ? "\n" : " "); }
void pu(set<int> v) { bool flag = false; for (auto dv : v) { if (flag) cout << " "; cout << dv; flag = true;} cout << endl;}
void pu(set<i64> v) { bool flag = false; for (auto dv : v) { if (flag) cout << " "; cout << dv; flag = true;} cout << endl;}
void pu(multiset<int> v) { bool flag = false; for (auto dv : v) { if (flag) cout << " "; cout << dv; flag = true;} cout << endl; }
void pu(multiset<i64> v) { bool flag = false; for (auto dv : v) { if (flag) cout << " "; cout << dv; flag = true;} cout << endl; }
//comb
i64 comb(const i64& n, const i64& k) {
i64 ret = 1;
for (i64 i = 1; i <= k; i++) {
ret *= n + 1 - i;
ret /= i;
}
return ret;
}
struct cord {
//support coordinate compression
public:
cord() : cord(vector<i64> {}) {}
explicit cord (const vector<i64>& v) : ov(v), cv(v) {
set<i64> s(v.begin(), v.end());
int cnt = 0;
for (auto x : s) { conv[x] = cnt++; }
for (auto &x : cv) { x = conv[x]; }
for (auto [k, u] : conv) { rconv[u] = k; }
conv[I64F] = cnt;
}
//ex
//index {0, 1, 2, 3, 4, 5}
//original value {5, 9, 3, 1, 6, 3}
//compressed value {2, 4, 1, 0, 3, 1}
//input:index
//output:compressed value
i64 &operator[](int i) {
assert(0 <= i and i < (int)cv.size());
return cv[i];
}
//input:compressed value
//output:original value
i64 get(int v) {
assert(rconv.find(v) != rconv.end());
return rconv[v];
}
int size() const { return (int)rconv.size(); }
//input:original value
//output:index
int lower_bound(i64 v) { return conv.lower_bound(v) -> second;}
int upper_bound(i64 v) { return conv.upper_bound(v) -> second;}
private:
//original, compressed
vector<i64> ov, cv;
//key:original value, value:compressed value
map<i64, int> conv;
//key:compressed value, value:origirnal value
map<int, i64> rconv;
};
//factorial
template<class T> class factorial {
private:
vector<T> fact;
vector<T> ifact;
public:
factorial(const int& n) : fact(n + 1), ifact(n + 1) {
fact[0] = 1;
for (int i = 1; i <= n; i++) {
fact[i] = fact[i - 1] * i;
}
ifact[n] = fact[n].inv();
for (int i = n; i >= 1; i--) {
ifact[i - 1] = ifact[i] * i;
}
}
T comb(const int& n, const int& k) {
if (k < 0 or k > n) {
return 0;
}
return fact[n] * ifact[k] * ifact[n - k];
}
T get(const int& n) { return fact[n]; }
T inv(const int& n) { return ifact[n]; }
};
//lca
template<class T> struct lca {
public:
lca(int n_) : n(n_), to(n), co(n), dep(n), costs(n) {
l = 0;
while ((1 << l) < n) { l++; }
par = vector<vector<int>>(n + 1, vector<int>(l, n));
}
void add_edge(int a, int b, T c = 1) {
to[a].push_back(b);
co[a].push_back(c);
to[b].push_back(a);
co[b].push_back(c);
}
void init(int root_ = 0) {
root = root_;
dfs(root);
for (int i = 0; i < l - 1; i++) {
for (int v = 0; v < n; v++) {
par[v][i + 1] = par[par[v][i]][i];
}
}
}
int get(int a, int b) {
if (dep[a] > dep[b]) { swap(a, b); }
int gap = dep[b] - dep[a];
for (int i = l - 1; i >= 0; i--) {
int len = 1 << i;
if (gap >= len) {
gap -= len;
b = par[b][i];
}
}
if (a == b) { return a; }
for (int i = l - 1; i >= 0; i--) {
int na = par[a][i];
int nb = par[b][i];
if (na != nb) { a = na, b = nb; }
}
return par[a][0];
}
T dist(int a, int b) {
int c = get(a, b);
return costs[a] + costs[b] - costs[c] * 2;
}
private:
int n, root, l;
vector<vector<int>> to;
vector<vector<T>> co; //cost
vector<int> dep;
vector<T> costs; //costs sum
vector<vector<int>> par;
void dfs(int v, int d = 0, T c = 0, int p = -1) {
if (p != -1) { par[v][0] = p; }
dep[v] = d;
costs[v] = c;
for (int i = 0; i < to[v].size(); i++) {
int u = to[v][i];
if (u == p) { continue; }
dfs(u, d + 1, c + co[v][i], v);
}
}
};
//matrix_ex
template<class T> class matrix_ex {
private:
int n;
vector<vector<T>> rec_relation;
vector<vector<T>> multipl_sqare(const vector<vector<T>>& lhs,
const vector<vector<T>>& rhs) {
vector ret(n, vector<T>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
ret[i][j] += lhs[i][k] * rhs[k][j];
}
}
}
return ret;
}
vector<T> multipl(const vector<vector<T>>& lhs, const vector<T>& rhs) {
vector<T> ret(n, 0);
for (int i = 0; i < n; i++) {
for (int k = 0; k < n; k++) {
ret[i] += lhs[i][k] * rhs[k];
}
}
return ret;
}
public:
matrix_ex(const vector<vector<T>>& vec_in) : n(vec_in.size()) {
rec_relation = vector<vector<T>>(n, vector<T>(n));
rec_relation = vec_in;
}
vector<T> get_ans(i64 t, const vector<T>& vec_in) {
vector ret(n, vector<T>(n, 0));
for (int i = 0; i < n; i++) {
ret[i][i] = 1;
}
while (t) {
if ((t % 2LL) == 0LL) {
rec_relation = multipl_sqare(rec_relation, rec_relation);
t >>= 1LL;
} else {
ret = multipl_sqare(rec_relation, ret);
t--;
}
}
return multipl(ret, vec_in);
}
};
//prime
struct prime {
public:
prime() : isp(1e7) {}
explicit prime (int n) : _n(n), isp(vector<_bool>(n + 1, true)), mfact(vector<int>(n + 1, -1)) {
isp[0] = isp[1] = false;
mfact[0] = mfact[1] = 1;
for (int i = 2; i <= n; i++) {
if (isp[i]) {
ps.push_back(i);
mfact[i] = i;
for (int j = 2 * i; j <= n; j += i) {
isp[j] = false;
if (mfact[j] == -1) { mfact[j] = i; }
}
}
}
}
vector<l_l> fast_get(int n) {
vector<l_l> ret;
assert(0 < n and n <= _n);
int i = -1;
while (n > 1) {
if (i == -1 or ret[i].first != mfact[n]) {
ret.push_back({mfact[n], 0});
i++;
}
n /= mfact[n];
ret[i].second++;
}
return ret;
}
vector<l_l> get(i64 n) {
vector<l_l> ret;
assert(0 < n and n <= ps.back() * ps.back());
int i = 0, cnt = -1;
while (ps[i] * ps[i] <= n) {
if (n % ps[i] == 0) {
ret.push_back({ps[i], 1});
cnt++;
n /= ps[i];
while (n % ps[i] == 0) {
n /= ps[i];
ret[cnt].second++;
}
}
i++;
if (i == ps.size()) { break; }
}
if (n > 1) ret.push_back({n, 1});
return ret;
}
bool operator[](int n) {
assert(0 < n and n <= _n);
return isp[n];
}
vector<i64> get_all(i64 n) {
i64 i = 1;
vector<i64> ret;
while (i * i <= n) {
if (n % i == 0) {
ret.push_back(i);
if (n / i != i) { ret.push_back(n / i); }
}
i++;
}
sort(ret.begin(), ret.end());
return ret;
}
private:
int _n;
vector<_bool> isp; //is-prime
vector<i64> ps; //primes
vector<int> mfact;
};
//rolling hash
const unsigned bases[64] = {257, 262, 266, 275, 276, 281, 285, 290, 296, 302, 306, 310, 311, 313, 323, 333, 344, 345, 350, 357, 367, 370, 373, 402,
    423, 425, 431, 440, 442, 443, 454, 457, 458, 462, 471, 478, 481, 487, 489, 492, 499, 501, 502, 503, 506, 514, 524, 532, 535, 541, 550, 552, 557,
    559, 562, 563, 567, 570, 571, 580, 592, 597, 604, 612};
const u64 mod = 0x1fffffffffffffff, base = bases[chrono::duration_cast<chrono::microseconds>(chrono::system_clock::now().time_since_epoch()).count()
    & 63];
struct rollinghash {
public:
rollinghash() : rollinghash("") {}
explicit rollinghash (const string &s) {
i64 n = s.size();
hashed.assign(n + 1, 0);
power.assign(n + 1, 0);
power[0] = 1;
for (i64 i = 0; i < n; i++) {
power[i + 1] = mul(power[i], base);
hashed[i + 1] = mul(hashed[i], base) + s[i];
if (hashed[i + 1] >= mod) { hashed[i + 1] -= mod; }
}
}
u64 get(i64 l, i64 r) const {
u64 ret = hashed[r] + mod - mul(hashed[l], power[r - l]);
if (ret >= mod) { ret -= mod; }
return ret;
}
u64 connect(u64 h1, u64 h2, i64 h2len) const {
u64 ret = mul(h1, power[h2len]) + h2;
if (ret >= mod) { ret -= mod; }
return ret;
}
void connect(const string &s) {
i64 n = hashed.size() - 1, m = s.size();
hashed.resize(n + m + 1);
power.resize(n + m + 1);
for (i64 i = n; i < n + m; i++) {
power[i + 1] = mul(power[i], base);
hashed[i + 1] = mul(hashed[i], base) + s[i - n];
if (hashed[i + 1] >= mod) { hashed[i + 1] -= mod; }
}
}
i64 LCP(const rollinghash &b, i64 l1, i64 r1, i64 l2, i64 r2) {
i64 len = min(r1 - l1, r2 - l2);
i64 low = -1, high = len + 1;
while (high - low > 1) {
i64 mid = (low + high) / 2;
if (get(l1, l1 + mid) == b.get(l2, l2 + mid)) { low = mid; }
else { high = mid; }
}
return low;
}
private:
vector<u64> hashed, power;
static constexpr u64 mask(i64 a) { return (1ull << a) - 1; }
inline u64 mul(u64 a, u64 b) const {
u64 a31 = a >> 31, b31 = b >> 31;
a &= mask(31);
b &= mask(31);
u64 x = a * b31 + b * a31;
u64 ans = (a31 * b31 << 1) + (x >> 30) + ((x & mask(30)) << 31) + a * b;
ans = (ans >> 61) + (ans & mod);
if (ans >= mod) { ans -= mod; }
return ans;
}
};
template<class T> vector<vector<T>> rot(const vector<vector<T>> &v) {
vector<vector<T>> ret = v;
int n = v.size();
rep(i, n) assert(n == v[i].size());
rep(i, n) {
rep(j, n) {
ret[i][j] = v[j][n - 1 - i];
}
}
return ret;
}
template<class T>void warshall_floyd(T& co) {
int n = co.size();
rep(k, n) rep(i, n) rep(j, n) {
if (co[i][k] == INF) { continue; }
if (co[k][j] == INF) { continue; }
chmin(co[i][j], co[i][k] + co[k][j]);
}
}
// end of template
// *INDENT-ON*
int main() {
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n; cin >> n;
scc_graph g(n);
vector<int> l(n);
vector to(n, vector<int>());
rep(i, n - 1) {
int a; cin >> l[i + 1] >> a;
a--;
to[a].push_back(i + 1);
g.add_edge(a, i + 1);
}
auto p = g.scc();
vector dp(n, -1);
dp[0] = 0;
// assert(p[0][0] == 0);
for (auto v : p) {
for (auto u : v) {
if (dp[u] == -1) { continue; }
chmax(dp[u], l[u]);
for (auto w : to[u]) {
chmax(dp[w], dp[u]);
}
}
}
map<int, int> mp;
for (auto d : dp) {
if (d >= 0) {
mp[d]++;
}
}
int now = 0;
for (auto& [k, v] : mp) {
now += v;
v = now;
}
int q; cin >> q;
rep(i, q) {
int op; cin >> op;
if (op == 1) {
int x; cin >> x;
auto it = mp.upper_bound(x);
cout << prev(it)->second << endl;
} else {
int y; cin >> y;
cout << dp[y - 1] << endl;
}
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0