Submission #444127

#TimeUsernameProblemLanguageResultExecution timeMemory
444127leinad2Dungeons Game (IOI21_dungeons)C++17
0 / 100
6 ms1100 KiB
#include "dungeons.h" #include<bits/stdc++.h> using namespace std; int N, i, j, sparse2[400010][20]; long long A[400010], sparse3[400010][20]; vector<int>S, P, W, L; void init(int n, vector<int>s, vector<int>p, vector<int>w, vector<int>l) { N=n;S=s;P=p;W=w;L=l;W.push_back(N);S.push_back(0);L.push_back(N);P.push_back(0); for(i=n-1;i>=0;i--)A[i]=A[W[i]]+S[i]; for(i=0;i<=n;i++)sparse2[i][0]=L[i],sparse3[i][0]=P[i]; for(j=1;j<20;j++)for(i=0;i<=n;i++)sparse2[i][j]=sparse2[sparse2[i][j-1]][j-1],sparse3[i][j]=sparse3[i][j-1]+sparse3[sparse2[i][j-1]][j-1]; } long long simulate(int x, int Z) { long long z=Z, s=S[0]; if(z<s) { for(j=19;j>=0;j--) { if(z+sparse3[x][j]<s) { z+=sparse3[x][j]; x=sparse2[x][j]; } }assert(z!=Z); z+=P[x]; x=L[x]; } z+=A[x]; return 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...