結果
問題 | No.2325 Skill Tree |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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_popcountconstexpr 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; }//combi64 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 compressionpublic: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 valuei64 &operator[](int i) {assert(0 <= i and i < (int)cv.size());return cv[i];}//input:compressed value//output:original valuei64 get(int v) {assert(rconv.find(v) != rconv.end());return rconv[v];}int size() const { return (int)rconv.size(); }//input:original value//output:indexint lower_bound(i64 v) { return conv.lower_bound(v) -> second;}int upper_bound(i64 v) { return conv.upper_bound(v) -> second;}private://original, compressedvector<i64> ov, cv;//key:original value, value:compressed valuemap<i64, int> conv;//key:compressed value, value:origirnal valuemap<int, i64> rconv;};//factorialtemplate<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]; }};//lcatemplate<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; //costvector<int> dep;vector<T> costs; //costs sumvector<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_extemplate<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);}};//primestruct 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-primevector<i64> ps; //primesvector<int> mfact;};//rolling hashconst 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;}