Submission #1986017
Source Code Expand
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#define _SCL_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#define push_back pb
#define make_pair mp
#define first x
#define second y
#include <cassert>
#include <ciso646>
#include <climits>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <array>
#include <bitset>
#include <deque>
#include <forward_list>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <algorithm>
#include <complex>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <locale>
#include <numeric>
#include <regex>
#include <string>
#include <utility>
#include <fstream>
#include <iostream>
#include <sstream>
#include <iomanip>
#ifdef LOCAL
//#include <vld.h>
#endif //LOCAL
using namespace std;
typedef long long ll;
typedef long double ld;
#define speedup cout.tie(nullptr);cin.tie(nullptr);ios_base::sync_with_stdio(false)
#define coutdouble cout<<setprecision(20);cout<<fixed
#define all(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
/*------CommentInInteractive--------*/
#ifndef LOCAL
#define endl "\n"
#endif //LOCAL
/*----------------------------------*/
const int INF = 1000 * 1000 * 1000 + 322;
const ll LLINF = 2LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL + 57;
const ll MOD = 1000 * 1000 * 1000 + 7;
const int RMOD = MOD - 2;
const int N = 200 * 1000 + 57;
const int P1M = 1336337; //Large prime ( ~1M )
const int P1K = 1009; //Big prime ( ~1K )
const ld EPS = 1e-9;
const ld PI = 3.1415926535897932384626433832795;
/*------------------------------------------------IO_OPERATORS---------------------------------------------*/
template<typename T, typename U> inline ostream &operator << (ostream &_out, const pair<T, U> &_p) { _out << _p.first << " " << _p.second; return _out; }
template<typename T, typename U> inline istream &operator >> (istream &_in, pair<T, U> &_p) { _in >> _p.first >> _p.second; return _in; }
template<typename T> inline ostream &operator << (ostream &_out, const vector<T> &_v) { if (_v.empty()) return _out; _out << _v.front(); for (auto _it = ++_v.begin(); _it != _v.end(); ++_it) _out << ' ' << *_it; return _out; }
template<typename T> inline istream &operator >> (istream &_in, vector<T> &_v) { for (auto &_i : _v) _in >> _i; return _in; }
template<typename T> inline ostream &operator << (ostream &_out, const set<T> &_s) { if (_s.empty()) return _out; _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) _out << ' ' << *_it; return _out; }
template<typename T> inline ostream &operator << (ostream &_out, const multiset<T> &_s) { if (_s.empty()) return _out; _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) _out << ' ' << *_it; return _out; }
template<typename T> inline ostream &operator << (ostream &_out, const unordered_set<T> &_s) { if (_s.empty()) return _out; _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) _out << ' ' << *_it; return _out; }
template<typename T> inline ostream &operator << (ostream &_out, const unordered_multiset<T> &_s) { if (_s.empty()) return _out; _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) _out << ' ' << *_it; return _out; }
template<typename T, typename U> inline ostream &operator << (ostream &_out, const map<T, U> &_m) { if (_m.empty()) return _out; _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) _out << ", (" << _it->first << ": " << _it->second << ')'; return _out; }
template<typename T, typename U> inline ostream &operator << (ostream &_out, const unordered_map<T, U> &_m) { if (_m.empty()) return _out; _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) _out << ", (" << _it->first << ": " << _it->second << ')'; return _out; }
/*--------------------------------------------------IO_FILES-----------------------------------------------*/
const char * infile =
#ifdef LOCAL
"input.txt"
#else
""
#endif //LOCAL
;
const char * outfile =
#ifdef LOCAL
""
#else
""
#endif //LOCAL
;
/*-------------------------------------------------ALLOCATOR----------------------------------------------*/
//#define ALLOC_LOCAL
#ifdef ALLOC_LOCAL
const int ML_ = 200;
char mem_[ML_ * 1000000];
size_t ptr = 0;
void * operator new(size_t cnt) { if (ptr + cnt < sizeof mem_) { ptr += cnt; return mem_ + ptr - cnt; } else { ptr = cnt; return mem_; } }
void operator delete(void *) {}
#endif //ALLOC_LOCAL
/*----------------------------------------------------MATHS------------------------------------------------*/
inline ll gcd(ll a, ll b) { while (b) { a %= b; swap(a, b); } return a; }
inline ll lcm(ll a, ll b) { return a*b / gcd(a, b); }
inline ll pwm(ll xx, ll pow, ll MD = MOD) { ll mlt = 1; while (pow) { if (pow & 1) { mlt *= xx; xx *= xx; pow >>= 1; xx %= MD; mlt %= MD; } else { pow >>= 1; xx *= xx; xx %= MD; } }return mlt; }
inline ll pw(ll xx, int pow) { ll mlt = 1; while (pow) { if (pow & 1) { mlt *= xx; xx *= xx; pow >>= 1; } else { pow >>= 1; xx *= xx; } }return mlt; }
inline ll inv(ll r) { return pwm(r, RMOD); }
/*--------------------------------------------------------------------------------------------------------*/
vector<int> g[N];
int on_lvl[N];
pair<ll,ll> dfs(int v, int lvl, int clvl = 0) {
ll al = 1, gd;
ll ml = 1;
vector<pair<ll, ll>> rt;
if (lvl == clvl) { return{ 1LL, 1LL }; }
for (auto u : g[v]) {
auto ret = dfs(u, lvl, clvl + 1);
al = al * (ret.x + ret.y) % MOD;
ml = (ml * ret.y) % MOD;
rt.pb(ret);
}
gd = 0;
for (int i = 0; i < sz(rt); ++i) {
gd += (ml * inv(rt[i].y) % MOD * rt[i].x) % MOD;
gd %= MOD;
}
pair<ll, ll> ans = {gd, ((al - gd) % MOD + MOD) % MOD};
return ans;
}
int dfs_lvl(int v, int lvl = 0) {
int rt = 0;
++on_lvl[lvl];
for (auto u : g[v]) {
rt = max(rt, dfs_lvl(u, lvl + 1));
}
return rt + 1;
}
inline void solve(ld tt) {
int n;
cin >> n;
vector<int> p(n);
cin >> p;
for (int i = 0; i < n; ++i) {
g[p[i]].pb(i + 1);
}
vector<pair<ll,ll>> ans;
ll acc = 1;
int max_lvl = dfs_lvl(0);
for (int lvl = 0; lvl < max_lvl; ++lvl) {
if(on_lvl[lvl] >= 3) ans.pb(dfs(0, lvl));
else if (on_lvl[lvl] == 2) ans.pb({2LL, 2LL});
else ans.pb({ 1LL, 1LL });
if (ans.back() == mp(0LL, 0LL)) {
ans.pop_back();
break;
}
acc *= ans.back().x + ans.back().y;
acc %= MOD;
}
//cout << ans << endl;
ll pr = 0;
for (int i = 0; i < sz(ans); ++i) {
pr += acc * inv(ans[i].x + ans[i].y) % MOD * ans[i].x % MOD;
pr %= MOD;
}
cout << pr << endl;
}
int main() {
ld tt = clock();
if (*infile != '\0')
freopen(infile, "r", stdin);
if (*outfile != '\0')
freopen(outfile, "w", stdout);
speedup;
coutdouble;
//int tst = 1;
//srand(time(NULL));
//cin >> tst;
//scanf("%d", &tst);
//while (tst-- > 0) {
//while(true) {
solve(tt);
//cout << "/*-----------------*/\n";
//}
#ifdef LOCAL
cout << "Time: " << ((ld)clock() - tt) / CLOCKS_PER_SEC << endl;
while (true);
#endif // LOCAL
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Smuggling Marbles |
User |
SendThemToHell |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
7703 Byte |
Status |
TLE |
Exec Time |
3156 ms |
Memory |
42480 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:188:36: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
freopen(infile, "r", stdin);
^
./Main.cpp:190:38: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
freopen(outfile, "w", stdout);
^
Judge Result
Set Name |
Sample |
Subtask1 |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
0 / 600 |
Status |
|
|
|
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 |
4 ms |
4992 KB |
00_example_02.txt |
AC |
4 ms |
4992 KB |
00_example_03.txt |
AC |
4 ms |
4992 KB |
s1_01.txt |
AC |
5 ms |
4992 KB |
s1_02.txt |
AC |
5 ms |
4992 KB |
s1_03.txt |
AC |
5 ms |
4992 KB |
s1_04.txt |
AC |
4 ms |
4992 KB |
s1_05.txt |
AC |
5 ms |
4992 KB |
s1_06.txt |
AC |
4 ms |
4992 KB |
s1_07.txt |
AC |
4 ms |
4992 KB |
s1_08.txt |
AC |
5 ms |
5120 KB |
s1_09.txt |
AC |
4 ms |
4992 KB |
s1_10.txt |
AC |
5 ms |
4992 KB |
s1_11.txt |
AC |
4 ms |
4992 KB |
s1_12.txt |
AC |
5 ms |
4992 KB |
s1_13.txt |
AC |
4 ms |
4992 KB |
s1_14.txt |
AC |
9 ms |
4992 KB |
s1_15.txt |
AC |
11 ms |
4992 KB |
s1_16.txt |
AC |
6 ms |
4992 KB |
s1_17.txt |
AC |
8 ms |
4992 KB |
s2_01.txt |
AC |
59 ms |
5248 KB |
s2_02.txt |
AC |
16 ms |
4992 KB |
s2_03.txt |
AC |
244 ms |
7040 KB |
s2_04.txt |
AC |
280 ms |
6528 KB |
s2_05.txt |
AC |
767 ms |
7936 KB |
s2_06.txt |
AC |
439 ms |
7936 KB |
s2_07.txt |
AC |
457 ms |
7296 KB |
s2_08.txt |
AC |
299 ms |
6144 KB |
s2_09.txt |
AC |
379 ms |
7936 KB |
s2_10.txt |
AC |
548 ms |
7680 KB |
s2_11.txt |
AC |
55 ms |
10992 KB |
s2_12.txt |
AC |
5 ms |
5120 KB |
s2_13.txt |
AC |
72 ms |
23924 KB |
s2_14.txt |
AC |
72 ms |
23284 KB |
s2_15.txt |
AC |
65 ms |
22512 KB |
s2_16.txt |
AC |
17 ms |
5248 KB |
s2_17.txt |
AC |
6 ms |
4992 KB |
s2_18.txt |
AC |
77 ms |
7424 KB |
s2_19.txt |
AC |
59 ms |
6400 KB |
s2_20.txt |
AC |
878 ms |
8960 KB |
s2_21.txt |
AC |
1397 ms |
9472 KB |
s2_22.txt |
AC |
427 ms |
8192 KB |
s2_23.txt |
AC |
873 ms |
8960 KB |
s2_24.txt |
TLE |
3156 ms |
11008 KB |
s2_25.txt |
TLE |
3156 ms |
12032 KB |
s2_26.txt |
TLE |
3156 ms |
12672 KB |
s2_27.txt |
TLE |
3156 ms |
22132 KB |
s2_28.txt |
TLE |
3156 ms |
18680 KB |
s2_29.txt |
AC |
1625 ms |
40560 KB |
s2_30.txt |
AC |
1718 ms |
42480 KB |
s2_31.txt |
AC |
1669 ms |
25716 KB |
s2_32.txt |
AC |
1778 ms |
25712 KB |