Submission #1773101
Source Code Expand
#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T> using vv=vector<vector<T>>;
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class T,size_t n> ostream& operator<<(ostream &os, const array<T,n> &t) {
os<<"{"; rep(i,n) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class S, class T,class U> ostream& operator<<(ostream &os, const tuple<S,T,U> &t) { return os<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class S, class T,class U,class V> ostream& operator<<(ostream &os, const tuple<S,T,U,V> &t) { return os<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<","<<get<3>(t)<<")";}
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
//#undef _DEBUG
#ifdef _DEBUG
#define out(args...){vector<string> a_r_g_s=s_p_l_i_t(#args, ','); e_r_r(a_r_g_s.begin(), args); }
vector<string> s_p_l_i_t(const string &s, char c){vector<string> v;int d=0,f=0;string t;for(char c:s){if(!d&&c==',')v.pb(t),t="";else t+=c;if(c=='\"'||c=='\'')f^=1;if(!f&&c=='(')++d;if(!f&&c==')')--d;}v.pb(t);return move(v);}
void e_r_r(vector<string>::iterator it) {}
template<typename T, typename... Args> void e_r_r(vector<string>::iterator it, T a, Args... args){ if(*it==" 1"||*it=="1") cerr<<endl; else cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << ", "; e_r_r(++it, args...);}
#else
#define out
#endif
template<typename T>vector<T> table(int n, T v){ return vector<T>(n, v);}
template <class... Args> auto table(int n, Args... args){auto val = table(args...); return vector<decltype(val)>(n, move(val));}
const ll MOD=1e9+7;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
template<class T> using SET=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
int main(){
ios_base::sync_with_stdio(false);
cout<<fixed<<setprecision(0);
// {
// SET<int> st;
// st.insert(1);
// st.insert(2);
// out(st.order_of_key(3),1);
// out(st.order_of_key(2),1);
// out(st.order_of_key(1),1);
// }
int n;
cin>>n;
vv<int> g(n);
vector<int> hs(n);
{
rep(i,n) cin>>hs[i];
reps(i,1,n){
int p;
cin>>p; --p;
hs[i]+=hs[p];
g[p].pb(i);
}
}
vector<int> Hs(n);
{
function<int(int)> dfs=[&](int v){
int re=hs[v];
for(int w:g[v])MX(re,dfs(w));
Hs[v]=re;
return re;
};
dfs(0);
}
SET<pii> st;
vector<int> res(n);
function<void(int)> dfs=[&](int v){
res[v]=g[v].size()+(st.size()-st.order_of_key(pii(hs[v]+1,0)));
for(int w:g[v]) st.insert(pii(Hs[w],w));
for(int w:g[v]){
st.erase(pii(Hs[w],w));
dfs(w);
st.insert(pii(Hs[w],w));
}
for(int w:g[v]) st.erase(pii(Hs[w],w));
};
dfs(0);
out(res,1);
unordered_map<int,int> re;
rep(i,n){
if(re.count(hs[i])) MN(re[hs[i]],res[i]+1);
else re[hs[i]]=res[i]+1;
}
int Q;
cin>>Q;
while(Q--){
int t;
cin>>t;
cout<<re[t]-1<<endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
I - 風船ツリー |
User |
nuip |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
4345 Byte |
Status |
AC |
Exec Time |
508 ms |
Memory |
22180 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample-01.txt, sample-02.txt |
All |
sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, sample-01.txt, sample-02.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
285 ms |
12580 KB |
01-02.txt |
AC |
1 ms |
256 KB |
01-03.txt |
AC |
1 ms |
256 KB |
01-04.txt |
AC |
267 ms |
7820 KB |
01-05.txt |
AC |
252 ms |
7820 KB |
01-06.txt |
AC |
261 ms |
7820 KB |
01-07.txt |
AC |
251 ms |
7692 KB |
01-08.txt |
AC |
254 ms |
7820 KB |
01-09.txt |
AC |
86 ms |
7564 KB |
01-10.txt |
AC |
508 ms |
10872 KB |
01-11.txt |
AC |
354 ms |
11000 KB |
01-12.txt |
AC |
354 ms |
11000 KB |
01-13.txt |
AC |
223 ms |
22180 KB |
01-14.txt |
AC |
240 ms |
22180 KB |
01-15.txt |
AC |
236 ms |
22180 KB |
01-16.txt |
AC |
273 ms |
13952 KB |
01-17.txt |
AC |
276 ms |
13952 KB |
01-18.txt |
AC |
273 ms |
15488 KB |
01-19.txt |
AC |
214 ms |
5632 KB |
01-20.txt |
AC |
217 ms |
4736 KB |
01-21.txt |
AC |
232 ms |
4480 KB |
01-22.txt |
AC |
252 ms |
4480 KB |
01-23.txt |
AC |
325 ms |
5632 KB |
01-24.txt |
AC |
228 ms |
7564 KB |
01-25.txt |
AC |
238 ms |
5888 KB |
01-26.txt |
AC |
252 ms |
5632 KB |
01-27.txt |
AC |
272 ms |
5376 KB |
01-28.txt |
AC |
312 ms |
7168 KB |
01-29.txt |
AC |
257 ms |
8972 KB |
01-30.txt |
AC |
252 ms |
8204 KB |
01-31.txt |
AC |
258 ms |
8332 KB |
sample-01.txt |
AC |
1 ms |
256 KB |
sample-02.txt |
AC |
1 ms |
256 KB |