Submission #1205686

#TimeUsernameProblemLanguageResultExecution timeMemory
1205686simona1230Dungeons Game (IOI21_dungeons)C++20
37 / 100
7104 ms1976960 KiB
#include "dungeons.h" #include <bits/stdc++.h> using namespace std; const int maxn=4*1e5+5; const int logg=24; const int base=8; int n; vector<int> s,p,w,l,h; vector<long long> v; int c,done[maxn]; long long sum[maxn][25][10]; int ver[maxn][25][10]; long long lim[maxn][25][10]; void construct(int x) { //cout<<x<<"! "<<endl; for(int i=0; i<n; i++) { if(v[x]>=s[i]) { ver[i][0][x]=w[i]; sum[i][0][x]=s[i]; lim[i][0][x]=1e18; } else { ver[i][0][x]=l[i]; sum[i][0][x]=p[i]; lim[i][0][x]=s[i]; } } ver[n][0][x]=n; lim[n][0][x]=1e18; for(int j=1; j<=logg; j++) for(int i=0; i<=n; i++) { sum[i][j][x]=sum[i][j-1][x]+sum[ver[i][j-1][x]][j-1][x]; if(1e18-sum[i][j-1][x]<sum[ver[i][j-1][x]][j-1][x])sum[i][j][x]=1e18; ver[i][j][x]=ver[ver[i][j-1][x]][j-1][x]; long long here=lim[ver[i][j-1][x]][j-1][x]-sum[i][j-1][x]; if(lim[ver[i][j-1][x]][j-1][x]==1e18)here=1e18; lim[i][j][x]=min(lim[i][j-1][x],here); //cout<<i<<" "<<j<<" "<<x<<" "<<ver[i][j][x]<<" "<<sum[i][j][x]<<" "<<lim[i][j][x]<<endl; } } void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) { n=N; s=S; p=P; w=W; l=L; int pw=1; v={1}; while(pw*base<=1e7) { pw*=base; v.push_back(pw); } v.push_back(1e18); for(int i=0;i<v.size();i++) construct(i); return; } long long simulate(int x, int zz) { long long z=zz; long long num=0; int in=0; while(num<v.size()&&x!=n) { while(num+1<v.size()&&z>=v[num+1])num++; //cout<<x<<" - "<<z<<" "<<num<<endl; for(int j=logg;j>=0;j--) { //cout<<x<<" "<<j<<" "<<num<<" "<<lim[x][j][num]<<endl; if(z<lim[x][j][num]) { //cout<<"in "<<z<<endl; z+=sum[x][j][num]; x=ver[x][j][num]; } } //cout<<x<<" "<<z<<endl; if(x==n)return z; if(z>=s[x]) { z+=s[x]; x=w[x]; } } return z; } /*int main() { while(1) { int nn=100; vector<int> ss,pp,ww,ll; int r=1e7; for(int i=0;i<nn;i++) ss.push_back(r); for(int i=0;i<nn;i++) pp.push_back(rand()%10); for(int i=0;i<nn;i++) ww.push_back(min(nn,rand()%2+1+i)); for(int i=0;i<nn;i++) ll.push_back(rand()%(nn+1)); init(nn,ss,pp,ww,ll); cout<<nn<<" "<<5<<endl; for(int i=0;i<ss.size();i++) cout<<ss[i]<<" "; cout<<endl; for(int i=0;i<pp.size();i++) cout<<pp[i]<<" "; cout<<endl; for(int i=0;i<ww.size();i++) cout<<ww[i]<<" "; cout<<endl; for(int i=0;i<ll.size();i++) cout<<ll[i]<<" "; cout<<endl; for(int i=1;i<=5;i++) { int xx,zz; xx=rand()%nn; zz=rand()%10; cout<<xx<<" "<<zz<<endl; cout<<simulate(xx,zz)<<endl; } } }*/
#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...