Submission #1986012
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[i] >= 3) ans.pb(dfs(0, lvl)); else if (on_lvl[i] == 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 | 0 |
Code Size | 7699 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘void solve(ld)’: ./Main.cpp:165:19: error: ‘i’ was not declared in this scope if(on_lvl[i] >= 3) ans.pb(dfs(0, lvl)); ^ ./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); ^