Submission #612314

#TimeUsernameProblemLanguageResultExecution timeMemory
612314StrawHatWessDungeons Game (IOI21_dungeons)C++17
37 / 100
7071 ms257704 KiB
#include "dungeons.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int>vi; #define pb push_back #define sz(x) (int)x.size() #define all(x) begin(x),end(x) #define FOR(i,a,b) for(int i=a; i<b; i++) #define ROF(i,a,b) for(int i=b-1; i>=a; i--) //------------------------------------------------ const int MX=4e5+10, LOG=25; int N; vi s, p, w, l; ll jump[MX][LOG], jumpSum[MX][LOG], jumpMX[MX][LOG]; void init(int n, vi s, vi p, vi w, vi l) { N=n; ::s=s; ::p=p; ::w=w; ::l=l; ::s.pb(0); ::p.pb(0); ::w.pb(N); ::l.pb(N); ROF(i,0,N+1){ if(i==N){ FOR(j,0,LOG) jump[i][j]=i, jumpSum[i][j]=0, jumpMX[i][j]=0; } else{ jump[i][0]=w[i]; jumpSum[i][0]=s[i]; jumpMX[i][0]=max(s[i], s[w[i]]); FOR(j,1,LOG){ jump[i][j]=jump[jump[i][j-1]][j-1]; jumpSum[i][j]=jumpSum[i][j-1] + jumpSum[jump[i][j-1]][j-1]; jumpMX[i][j]=max(jumpMX[i][j-1], jumpMX[jump[i][j-1]][j-1]); } } } } ll simulate(int st, int x){ int u=st; ll X=x; while(1){ if(u==N) break; if(X>=s[u]){ ROF(i,0,LOG) if(jumpMX[u][i]<=X){ X+=jumpSum[u][i]; u=jump[u][i]; } X+=jumpSum[u][0]; u=jump[u][0]; } else{ X+=p[u]; u=l[u]; } } return X; } /* 3 2 2 6 9 3 1 2 2 2 3 1 0 1 0 1 2 3 24 25 */
#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...