結果

問題 No.2325 Skill Tree
ユーザー hamathhamath
提出日時 2023-05-28 15:50:16
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 317 ms / 3,000 ms
コード長 10,306 bytes
コンパイル時間 4,799 ms
コンパイル使用メモリ 233,328 KB
実行使用メモリ 25,740 KB
最終ジャッジ日時 2024-12-27 09:02:10
合計ジャッジ時間 16,052 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 3 ms
5,248 KB
testcase_03 AC 13 ms
5,248 KB
testcase_04 AC 3 ms
5,248 KB
testcase_05 AC 3 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 76 ms
9,488 KB
testcase_08 AC 72 ms
10,708 KB
testcase_09 AC 95 ms
11,664 KB
testcase_10 AC 106 ms
14,224 KB
testcase_11 AC 115 ms
13,744 KB
testcase_12 AC 232 ms
23,608 KB
testcase_13 AC 231 ms
23,616 KB
testcase_14 AC 226 ms
23,612 KB
testcase_15 AC 222 ms
23,612 KB
testcase_16 AC 231 ms
23,612 KB
testcase_17 AC 194 ms
21,056 KB
testcase_18 AC 192 ms
21,052 KB
testcase_19 AC 191 ms
21,048 KB
testcase_20 AC 177 ms
21,044 KB
testcase_21 AC 178 ms
21,052 KB
testcase_22 AC 249 ms
25,588 KB
testcase_23 AC 276 ms
25,592 KB
testcase_24 AC 270 ms
25,592 KB
testcase_25 AC 262 ms
25,592 KB
testcase_26 AC 270 ms
25,592 KB
testcase_27 AC 290 ms
23,432 KB
testcase_28 AC 277 ms
23,440 KB
testcase_29 AC 282 ms
23,436 KB
testcase_30 AC 289 ms
23,380 KB
testcase_31 AC 290 ms
23,436 KB
testcase_32 AC 224 ms
20,948 KB
testcase_33 AC 245 ms
21,072 KB
testcase_34 AC 238 ms
21,076 KB
testcase_35 AC 307 ms
25,612 KB
testcase_36 AC 301 ms
25,612 KB
testcase_37 AC 317 ms
25,740 KB
権限があれば一括ダウンロードができます

ソースコード

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

#ifdef LOCAL
//#define _GLIBCXX_DEBUG
#else
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx512f,avx512dq,avx512cd,avx512bw,avx512vl")
#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<char> Vc;
typedef vector<P> VP;
typedef vector<VP> VVP;
typedef vector<Vec> VV;
typedef vector<Vi> VVi;
typedef vector<Vc> VVc;
typedef vector<VV> VVV;
typedef vector<VVV> VVVV;
#define MAKEVV(variable, a, ...) VV variable(a, Vec(__VA_ARGS__))
#define MAKEVVc(variable, a, ...) VVc variable(a,Vc(__VA_ARGS__))
#define MAKEVVV(variable, a, b, ...) VVV variable(a, VV(b, Vec(__VA_ARGS__)))
#define MAKEVVVV(variable, a, b, c, ...) VVVV variable(a, VVV(b, (VV(c, Vec(__VA_ARGS__)))))
#define endl '\n'
#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
const ll INF = 4'000'000'000'000'000'010LL;
const ll MOD=998244353;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define rEach(i, mp) for (auto i = mp.rbegin(); i != mp.rend(); ++i)
#define SUM(a) accumulate(ALL(a),0LL)
#define outminusone(a) cout<< ( a==INF ? -1 : a ) <<endl
#define Uniq(v) v.erase(unique(v.begin(), v.end()), v.end())
#define fi first
#define se second
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>auto lb(vector<T> &X, T x){return lower_bound(ALL(X),x) - X.begin();}
template<class T>auto ub(vector<T> &X, T x){return upper_bound(ALL(X),x) - X.begin();}
ll popcnt(ll x){return __builtin_popcount(x);}
ll topbit(ll t){return t==0?-1:63-__builtin_clzll(t);}
ll floor(ll y,ll x){assert(x != 0);if(x < 0){y *= -1; x *= -1;}if(y < 0){return (y-x+1)/x;}return y/x;};
ll ceil(ll y, ll x){assert(x != 0);if(x < 0){y *= -1; x *= -1;}if(y < 0){return y/x;}return (y+x-1)/x;};
template<typename T1, typename T2>istream &operator>>(istream &i, pair<T1, T2> &p) { return i>>p.first>>p.second; }
template<typename T>istream& operator>>(istream&i,vector<T>&v){rep(j,v.size())i>>v[j];return i;}
template<typename T1, typename T2>ostream &operator<<(ostream &s, const pair<T1, T2> &p) { return s<<"("<<p.first<<", "<<p.second<<")"; }
template<class T>ostream &operator<<(ostream &os, const vector<T> &v) {bool f = false;for(const auto &d: v) {if(f) os<<" ";f = true;os<<d;}return os
    ;}
template <class T> ostream& operator<<(ostream& os, const set<T>& s) {os << "{";bool f = false;for (auto d : s) {if (f) os << ", ";f = true;os << d
    ;}return os << "}";}
template <class T> ostream& operator<<(ostream& os, const multiset<T>& s) {os << "{";bool f = false;for (auto d : s) {if (f) os << ", ";f = true;os
    << d;}return os << "}";}
template<class T, class U>ostream &operator<<(ostream &os, const map<T, U> &s) {bool f = false;os<<endl;for(auto p: s) {if(f) os<<endl;f = true;os<<p
    .first<<": "<<p.second;}return os<<endl;}
void out() { cout << endl; }
template <class Head, class... Tail> void out(const Head &head, const Tail &...tail) {cout << head;if(sizeof...(tail)) cout << ' ';out(tail...);}
#ifdef LOCAL
template<typename T>ostream &operator<<(ostream &s, const vector<vector<T>> &vv) {int len=vv.size();for(int i=0; i<len; ++i) {if(i==0)s<<endl;s<<i<<"
    :"<<vv[i];if(i!=len-1)s<<endl;}return s;}
struct PrettyOS {ostream& os;bool first;template <class T> auto operator<<(T&& x) {if (!first) os << ", ";first = false;os << x;return *this;}};
template <class... T> void dbg0(T&&... t) {(PrettyOS{cerr, true} << ... << t);}
#define dbg(...)do {cerr << #__VA_ARGS__ << ": ";dbg0(__VA_ARGS__);cerr << endl;} while (false);
#else
#define dbg(...)
#endif
void vizGraph(VV &g, int directed = 0, string filename = "out.png") {
#ifdef LOCAL
ofstream ofs("./out.dot");
ofs<<"digraph graph_name {"<<endl;
set<P> memo;
rep(i, g.size()) {
rep(j, g[i].size()) {
if(!directed && (memo.count(P(i, g[i][j])))) {
continue;
}
//
memo.insert(P(g[i][j],i));
ofs<<" "<<i<<" -> "<<g[i][j]<<(!directed ? " [arrowhead = none]" : "")<<endl;
}
if(g[i].empty()){
ofs<<" "<<i<<endl;
}
}
ofs<<"}"<<endl;
ofs.close();
system(((string) "dot -T png out.dot >"+filename).c_str());
#else
#endif
}
void vizGraphWithValue(VV &g, Vec &dp, int directed = 0, string filename = "out.png") {
#ifdef LOCAL
ofstream ofs("./out.dot");
ofs<<"digraph graph_name {"<<endl;
set<P> memo;
auto node = [](ll ind, ll dp)->string {
return '"'+to_string(dp)+"("+to_string(ind)+")"+'"';
};
rep(i, g.size()) {
rep(j, g[i].size()) {
if(!directed && memo.count(P(i, g[i][j]))) {
continue;
}
memo.insert(P(g[i][j],i));
ofs<<" "<<node(i, dp[i])<<" -> "<<node(g[i][j], dp[g[i][j]])<<(!directed ? " [arrowhead = none]" : "")
<<endl;
}
if(g[i].empty()){
ofs<<" "<<node(i, dp[i])<<endl;
}
}
ofs<<"}"<<endl;
ofs.close();
system(((string) "dot -T png out.dot >"+filename).c_str());
#else
#endif
}
void vizWeightedGraph(VVP &g, int directed = 0, string filename = "out.png") {
#ifdef LOCAL
ofstream ofs("./out.dot");
ofs<<(directed ? "di" : "")<<"graph graph_name {"<<endl;
string arrow = (directed ? " -> " : " -- ");
set<P> used;
rep(i, g.size()) {
if(g[i].empty()){
ofs<<" "<<i<<endl;
continue;
}
rep(j, g[i].size()) {
if(used.count(mp(i, g[i][j].fi))) continue;
if(directed == 0) used.insert(pair<int, int>(g[i][j].fi, i));
ofs<<" "<<i<<arrow<<g[i][j].fi;
//
ofs<<" [ label = \""<<g[i][j].se<<"\"];";
ofs<<endl;
}
}
ofs<<"}"<<endl;
ofs.close();
system(((string) "dot -T png out.dot >"+filename).c_str());
#else
#endif
}
void vizWeightedGraphWithValue(VVP &g, Vec &dp, int directed = 0, string filename = "out.png") {
#ifdef LOCAL
ofstream ofs("./out.dot");
ofs<<(directed ? "di" : "")<<"graph graph_name {"<<endl;
string arrow = (directed ? " -> " : " -- ");
set<P> used;
auto node = [](ll ind, ll dp)->string {
return '"'+to_string(dp)+"("+to_string(ind)+")"+'"';
};
rep(i, g.size()) {
if(g[i].empty()){
ofs<<" "<<i<<endl;
continue;
}
rep(j, g[i].size()) {
if(used.count(mp(i, g[i][j].fi))) continue;
if(directed == 0) used.insert(pair<int, int>(g[i][j].fi, i));
ofs<<" "<<node(i, dp[i])<<arrow<<node(g[i][j].fi, dp[g[i][j].fi]);
//
ofs<<" [ label = \""<<g[i][j].se<<"\"];";
ofs<<endl;
}
}
ofs<<"}"<<endl;
ofs.close();
system(((string) "dot -T png out.dot >"+filename).c_str());
#else
#endif
}
template<typename T=ll>
struct Zip {
bool initialized;
vector<T> v;
Zip() : initialized(false) {}
void add(T x) { v.push_back(x); }
void init() {
sort(ALL(v));
Uniq(v);
initialized = true;
}
ll id(T x) {
if(!initialized) init();
return lb(v, x);
}
T operator[](ll i) {
if(!initialized) init();
return v[i];
}
ll size() {
if(!initialized) init();
return v.size();
}
};
int solve(){
/*
*
N
1,2,…,N
1 2≤i≤N i
Li Ai
Q
2
1 x: x
2 y: y
y −1
*/
ll n;
cin>>n;
VVP g(n);
REP(i,1,n){
ll l,a;
cin>>l>>a;
a--;
g[a].emplace_back(i,l);
}
vizWeightedGraph(g);
ll Q;
cin>>Q;
Vec dp(n,-1);
dp[0] = 0;
auto dfs = [&](auto &&self, ll v, ll p)->void {
Each(pir, g[v]) {
auto [x, l] = pir;
if(x != p) {
chmax(dp[x],dp[v]);
chmax(dp[x],l);
self(self, x, v);
}
}
};
dfs(dfs, 0, -1);
dbg(dp);
Vec ans(Q);
Zip<ll> zip;
rep(i,n){
zip.add(dp[i]);
}
VP Query(Q);
cin>>Query;
rep(i,Q){
auto [t,x] = Query[i];
if(t == 1){
zip.add(x);
}
}
zip.init();
ll sz = zip.size();
Vec s(sz);
rep(i,n){
if(dp[i] == -1)continue;
s[zip.id(dp[i])]++;
}
auto cumsum = [](Vec &v, ll off = 1){
ll n = v.size();
Vec cumv(n + 1);
rep(i,n) cumv[i+1] = v[i] + cumv[i];
if (off == 0) cumv.erase(cumv.begin());
return cumv;
};
Vec S = cumsum(s,0);
dbg(zip.v)
dbg(s);
dbg(S);
rep(i,Q){
auto [t,x] = Query[i];
if(t == 1){
out(S[zip.id(x)]);
}else{
x--;
out(dp[x]);
}
}
return 0;
}
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout<<std::setprecision(20);
// ll T;
// cin>>T;
// while(T--)
solve();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0