제출 #437142

#제출 시각아이디문제언어결과실행 시간메모리
437142jeroenodb던전 (IOI21_dungeons)C++17
26 / 100
1102 ms179516 KiB
#ifndef GRADER #include "dungeons.h" #endif // #pragma GCC optimize "Ofast" #include "bits/stdc++.h" using namespace std; #define all(x) begin(x),end(x) template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; } template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; } #define debug(a) cerr << "(" << #a << ": " << a << ")\n"; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> pi; const int mxN = 4e5+10, oo = 1e8; const int LOG = 25; int jmp[mxN][LOG], mn[mxN][LOG]; ll sm[mxN][LOG]; static int N; const int B = 7000; vi S,P,W,L; ll prefsum[mxN] = {}; void init(int n, vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) { S=s,P=p,W=w,L=l; N=n; jmp[n][0]=n; mn[n][0]=oo; sm[n][0]=1000; for(int j=0;j<n;++j) { if(s[j]>=B) { jmp[j][0] = l[j], sm[j][0]=p[j]; } else jmp[j][0] = w[j], sm[j][0] = s[j]; mn[j][0] = (s[j]>=B?s[j]:oo); } for(int i=1;i<LOG;++i) { for(int j=0;j<=n;++j) { jmp[j][i] = jmp[jmp[j][i-1]][i-1]; mn[j][i] = max(0LL,min((ll)mn[j][i-1],mn[jmp[j][i-1]][i-1]-sm[j][i-1])); sm[j][i] = sm[j][i-1]+sm[jmp[j][i-1]][i-1]; } } for(int i=n-1;i>=0;--i) { prefsum[i]=S[i]+prefsum[W[i]]; } } long long mysimulate(int x, ll z) { int n = N; while(z<B) { if(x==n) return z; if(z>=S[x]) { z+=S[x]; x=W[x]; } else { z+=P[x]; x=L[x]; } } // find next x: S[x]>z, can only happen log times // what if P[x] is very small? const int mxS = int(1e7); while(x!=n and z<mxS) { for(int i=LOG-1;i>=0 and z<mxS and x!=n;--i) { if(mn[x][i]>z) { z+=sm[x][i]; x=jmp[x][i]; } } if(x==n or z>=mxS) break; assert(S[x]>=B and z>=S[x]); if(z>=S[x]) { z+=S[x]; x=W[x]; } else { z+=P[x]; x=L[x]; } } return prefsum[x]+z; } long long simulate(int x, int z) { return mysimulate(x,z); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...