Submission #1986105

---

Source Code Expand

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

ll h[100];

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

const int MOD = 1e9 + 7;
int N;
vector <int> E[200020], A[200020];
set <int> F[200020];
int p2[200020];
int p[200020], pp[200020]; int Find(int x) { return p[x] == x ? x : p[x] = Find(p[x]); }

int pw(int x, int y = MOD - 2) {
	int res = 1;
	while(y) {
		if(y & 1) res = (ll) res * x % MOD;
		x = (ll) x * x % MOD;
		y >>= 1;
	}
	return res;
}

pii dfs(int x) {
	if(szz(F[x]) == 0) return pii(1, 1);
	vector <pii> v;
	for(int e : F[x]) {
		v.pb(dfs(e));
	}
	ll t1 = 1;
	for(pii e : v) t1 = t1 * (ll) (e.Fi + e.Se) % MOD;
	ll s = 1;
	for(pii e : v) s = s * (ll) e.Se % MOD;
	ll t2 = 0;
	for(pii e : v) t2 = (t2 + s * pw(e.Se) % MOD * e.Fi) % MOD;
	t1 -= t2; if(t1 < 0) t1 += MOD;
	return pii((int)t2, (int)t1);
}

void solve(){
	p2[0] = 1;
	for(int i=1;i<200020;i++) p2[i] = p2[i-1] * 2 % MOD;
	scanf("%d", &N);
	for(int i=1;i<=N;i++) {
		int x;
		scanf("%d", &x);
		E[x].pb(i);
	}
	for(int i=1;i<=N;i++) p[i] = i;
	int ans = p2[N];
	A[0].pb(0);
	for(int u=0;;u++) {
		for(int e : A[u]) {
			for(int f : E[e]) A[u+1].pb(f);
			if(szz(E[e]) == 0) {
				int par = pp[Find(e)];
				F[par].erase(Find(e));
				
				if(szz(F[par]) == 1 && par) {
					int ppar = pp[par];
					p[par] = ppar;
					int u = *F[par].begin();
					pp[u] = ppar;
					F[ppar].erase(par);
					F[ppar].insert(u); F[par].clear();
				}
			}
			else if(szz(E[e]) == 1) p[Find(E[e][0])] = Find(e);
			else {
				for(int f : E[e]) {
					F[Find(e)].insert(f); pp[f] = Find(e);
				}
			}
		}
		if(szz(A[u+1]) == 0) break;
		ans = (ans + dfs(0).Fi * (ll)p2[N + 1 - szz(A[u+1])]) % MOD;
	}
	printf("%d\n", ans);
}

int main(){
	int Tc = 1;// scanf("%d", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void solve()’:
./Main.cpp:103:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
./Main.cpp:106:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
                  ^

Judge Result