結果
問題 | No.2325 Skill Tree |
ユーザー | hamath |
提出日時 | 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 |
ソースコード
#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 secondtemplate<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 LOCALtemplate<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(...)#endifvoid vizGraph(VV &g, int directed = 0, string filename = "out.png") {#ifdef LOCALofstream 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 LOCALofstream 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 LOCALofstream 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 LOCALofstream 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();}