Submission #1195972

#TimeUsernameProblemLanguageResultExecution timeMemory
1195972LudisseyDungeons Game (IOI21_dungeons)C++20
25 / 100
518 ms234576 KiB
#include "dungeons.h" #include <bits/stdc++.h> #define int long long #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() using namespace std; int N; vector<int> s,p,w,l; vector<int> ss; vector<vector<vector<int>>> nxt; vector<vector<vector<int>>> nxp; vector<int> tw; const int LOG=26; int pth(int x){ if(x==N) return 0; if(tw[x]>=0) return tw[x]; tw[x]=pth(w[x])+s[x]; return tw[x]; } void init(signed n, std::vector<signed> S, std::vector<signed> P, std::vector<signed> W, std::vector<signed> L) { N=n; s.resize(N); tw.resize(N,-1); p.resize(N); w.resize(N+1); l.resize(N+1); nxt.resize(N+1,vector<vector<int>>(LOG,vector<int>(6,0))); nxp.resize(N+1,vector<vector<int>>(LOG,vector<int>(6,N))); l[N]=N; w[N]=N; set<int> st; st.insert(0); for (int i = 0; i < n; i++) { s[i]=S[i]; p[i]=P[i]; w[i]=W[i]; l[i]=L[i]; st.insert(s[i]); } for(auto u: st){ ss.push_back(u); } for (int i = 0; i < n; i++){ for (int j = 0; j < sz(ss); j++) { if(s[i]<=ss[j]){ nxt[i][0][j]=s[i]; nxp[i][0][j]=w[i]; }else{ nxt[i][0][j]=p[i]; nxp[i][0][j]=l[i]; } } } for (int j = 1; j < LOG; j++) { for (int i = 0; i < N; i++) { for (int k = 0; k < sz(ss); k++){ nxp[i][j][k]=nxp[nxp[i][j-1][k]][j-1][k]; nxt[i][j][k]=nxt[i][j-1][k]+nxt[nxp[i][j-1][k]][j-1][k]; } } } for (int i = 0; i < N; i++) pth(i); return; } long long simulate(signed x, signed z) { int cs=z; int u=x; for (int i = 0; i < sz(ss); i++) { if(ss[i+1]<=cs) continue; for (int j = LOG-1; j >= 0; j--) { if(nxp[u][j][i]==N||nxt[u][j][i]+cs>=ss[i+1]) continue; cs+=nxt[u][j][i]; u=nxp[u][j][i]; } if(nxp[u][0][i]==N){ if(s[u]>cs) cs+=p[u]; else cs+=s[u]; return cs; }else{ cs+=nxt[u][0][i]; u=nxp[u][0][i]; } } return cs+pth(u); }
#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...