제출 #960871

#제출 시각아이디문제언어결과실행 시간메모리
960871Warinchai던전 (IOI21_dungeons)C++17
0 / 100
671 ms613716 KiB
#include "dungeons.h" #include<bits/stdc++.h> using namespace std; int lift[17][17][50005]; long long mn[17][17][50005]; long long dis[17][17][50005]; long long inf=1e18+7; int N; vector<int>W; vector<int>S; vector<int>L; vector<int>P; void init(int n,vector<int> s,vector<int> p,vector<int> w,vector<int> l) { N=n; S=s; W=w; L=l; P=p; for(int i=0;i<17;i++){ int st=(1<<(i-1))+1; int en=(1<<i); for(int j=0;j<n;j++){ if(s[j]>en)lift[i][0][j]=l[j],mn[i][0][j]=inf,dis[i][0][j]=p[j]; else if(s[j]>=st)lift[i][0][j]=l[j],mn[i][0][j]=s[j],dis[i][0][j]=p[j]; else lift[i][0][j]=w[j],mn[i][0][j]=inf,dis[i][0][j]=s[j]; } lift[i][0][n]=n; mn[i][0][n]=0; for(int j=1;j<=16;j++){ for(int k=0;k<=n;k++){ lift[i][j][k]=lift[i][j-1][lift[i][j-1][k]]; dis[i][j][k]=dis[i][j-1][k]+dis[i][j-1][lift[i][j-1][k]]; mn[i][j][k]=min(mn[i][j-1][k],mn[i][j-1][lift[i][j-1][k]]-dis[i][j-1][k]); } } } //cerr<<"work\n"; return; } long long simulate(int x, int z) { //cerr<<"work\n"; long long c=1,lv=0; long long pow=z; while(x>(1<<c)){ lv=c; c++; } //cerr<<x<<"\n"; //cerr<<lv<<"\n"; while(1){ //cerr<<x<<" "<<pow<<"\n"; for(int i=15;i>=0;i--){ //cerr<<i<<" "<<lv<<" "<<x<<"\n"; if(pow<mn[lv][i][x]&&pow+dis[lv][i][x]<=(1<<lv))pow+=dis[lv][i][x],x=lift[lv][i][x]; } //cerr<<x<<" "<<pow<<"\n\n"; if(x==N)break; if(pow>S[x])pow+=S[x],x=W[x]; else { pow+=P[x]; x=L[x]; } lv++; } return pow; }
#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...