Submission #2203977


Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
template<unsigned int mod_>
struct ModInt{
	using uint = unsigned int;
	using ll = long long;
	using ull = unsigned long long;

	constexpr static uint mod = mod_;

	uint v;
	ModInt():v(0){}
	ModInt(ll v):v(normS(v%mod+mod)){}
	explicit operator bool() const {return v!=0;}
	static uint normS(const uint &x){return (x<mod)?x:x-mod;}		// [0 , 2*mod-1] -> [0 , mod-1]
	static ModInt make(const uint &x){ModInt m; m.v=x; return m;}
	ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));}
	ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));}
	ModInt operator-() const { return make(normS(mod-v)); }
	ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);}
	ModInt operator/(const ModInt& b) const { return *this*b.inv();}
	ModInt& operator+=(const ModInt& b){ return *this=*this+b;}
	ModInt& operator-=(const ModInt& b){ return *this=*this-b;}
	ModInt& operator*=(const ModInt& b){ return *this=*this*b;}
	ModInt& operator/=(const ModInt& b){ return *this=*this/b;}
	ll extgcd(ll a,ll b,ll &x,ll &y) const{
		ll u[]={a,1,0},v[]={b,0,1};
		while(*v){
			ll t=*u/ *v;
			rep(i,3) swap(u[i]-=t*v[i],v[i]);
		}
		if(u[0]<0) rep(i,3) u[i]=-u[i];
		x=u[1],y=u[2];
		return u[0];
	}
	ModInt inv() const{
		ll x,y;
		extgcd(v,mod,x,y);
		return make(normS(x+mod));
	}
	bool operator==(const ModInt& b) const { return v==b.v;}
	bool operator!=(const ModInt& b) const { return v!=b.v;}
	friend istream& operator>>(istream &o,ModInt& x){
		ll tmp;
		o>>tmp;
		x=ModInt(tmp);
		return o;
	}
	friend ostream& operator<<(ostream &o,const ModInt& x){ return o<<x.v;}
};
using mint = ModInt<1000000007>;

int N;
vector<vector<int>> G;
using T = array<mint,3>;	//0,1,geq 2
vector<deque<T>> dp;
vector<int> depth;

void dfs(int v){
	if(G[v].empty()){
		dp[v] = {{1,1,0}};
		return;
	}
	for(int u:G[v]){
		depth[u] = depth[v] + 1;
		dfs(u);
	}
	int max_len = 0, U = -1;
	for(int u:G[v]){
		if(dp[u].size() > max_len){
			max_len = dp[u].size();
			U = u;
		}
	}
	swap(dp[v],dp[U]);
	for(int u:G[v]) if(u!=U){
		rep(k,dp[u].size()){
			T t = {};
			rep(i,3) rep(j,2){
				t[min(2,i+j)] += dp[v][k][i]*dp[u][k][j];
			}
			dp[v][k] = t;
		}
	}
	rep(k,dp[v].size()) dp[v][k][0] += dp[v][k][2], dp[v][k][2] = 0;
	dp[v].push_front({1,1,0});
}
mint p2[200010];
int main(){
	p2[0] = 1;
	rep(i,200009) p2[i+1] = p2[i]*2;
	cin>>N;
	N++;
	G.resize(N);
	dp.resize(N);
	depth.resize(N);
	rep1(i,N-1){
		int p;
		cin>>p;
		G[p].pb(i);
	}
	dfs(0);
	vector<int> cnt(N);
	rep(i,N) cnt[depth[i]]++;
	mint ans = 0;
	rep(k,dp[0].size()){
		ans += dp[0][k][1] * p2[N-cnt[k]];
	}
	cout<<ans<<endl;
}

Submission Info

Submission Time
Task E - Smuggling Marbles
User sigma425
Language C++14 (GCC 5.4.1)
Score 400
Code Size 3330 Byte
Status TLE
Exec Time 3166 ms
Memory 239348 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 400 / 400 0 / 600
Status
AC × 3
AC × 20
AC × 43
TLE × 9
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
Subtask1 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt, s1_14.txt, s1_15.txt, s1_16.txt, s1_17.txt
All 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt, s1_14.txt, s1_15.txt, s1_16.txt, s1_17.txt, s2_01.txt, s2_02.txt, s2_03.txt, s2_04.txt, s2_05.txt, s2_06.txt, s2_07.txt, s2_08.txt, s2_09.txt, s2_10.txt, s2_11.txt, s2_12.txt, s2_13.txt, s2_14.txt, s2_15.txt, s2_16.txt, s2_17.txt, s2_18.txt, s2_19.txt, s2_20.txt, s2_21.txt, s2_22.txt, s2_23.txt, s2_24.txt, s2_25.txt, s2_26.txt, s2_27.txt, s2_28.txt, s2_29.txt, s2_30.txt, s2_31.txt, s2_32.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 2 ms 1024 KB
00_example_02.txt AC 2 ms 1024 KB
00_example_03.txt AC 2 ms 1024 KB
s1_01.txt AC 3 ms 1664 KB
s1_02.txt AC 3 ms 1536 KB
s1_03.txt AC 3 ms 2304 KB
s1_04.txt AC 2 ms 1152 KB
s1_05.txt AC 3 ms 1408 KB
s1_06.txt AC 4 ms 3456 KB
s1_07.txt AC 3 ms 1664 KB
s1_08.txt AC 16 ms 2944 KB
s1_09.txt AC 3 ms 1536 KB
s1_10.txt AC 4 ms 2944 KB
s1_11.txt AC 3 ms 1536 KB
s1_12.txt AC 3 ms 2176 KB
s1_13.txt AC 2 ms 1152 KB
s1_14.txt AC 4 ms 2944 KB
s1_15.txt AC 4 ms 2816 KB
s1_16.txt AC 4 ms 3072 KB
s1_17.txt AC 4 ms 2944 KB
s2_01.txt AC 20 ms 17024 KB
s2_02.txt AC 5 ms 3968 KB
s2_03.txt AC 182 ms 132992 KB
s2_04.txt AC 103 ms 74496 KB
s2_05.txt AC 182 ms 120960 KB
s2_06.txt AC 278 ms 192256 KB
s2_07.txt AC 158 ms 109184 KB
s2_08.txt AC 70 ms 51584 KB
s2_09.txt AC 272 ms 188288 KB
s2_10.txt AC 199 ms 132992 KB
s2_11.txt AC 222 ms 239348 KB
s2_12.txt AC 5 ms 4864 KB
s2_13.txt TLE 3166 ms 194432 KB
s2_14.txt TLE 3166 ms 194304 KB
s2_15.txt TLE 3164 ms 176640 KB
s2_16.txt AC 18 ms 17024 KB
s2_17.txt AC 5 ms 4096 KB
s2_18.txt AC 146 ms 123136 KB
s2_19.txt AC 85 ms 74368 KB
s2_20.txt AC 287 ms 191744 KB
s2_21.txt AC 290 ms 183296 KB
s2_22.txt AC 301 ms 206976 KB
s2_23.txt AC 304 ms 191744 KB
s2_24.txt AC 220 ms 160768 KB
s2_25.txt AC 292 ms 149632 KB
s2_26.txt AC 1107 ms 150400 KB
s2_27.txt TLE 3165 ms 176128 KB
s2_28.txt TLE 3164 ms 175232 KB
s2_29.txt TLE 3165 ms 195712 KB
s2_30.txt TLE 3165 ms 195712 KB
s2_31.txt TLE 3164 ms 167936 KB
s2_32.txt TLE 3165 ms 169728 KB