Submission #1276294

#TimeUsernameProblemLanguageResultExecution timeMemory
1276294MMihalevDungeons Game (IOI21_dungeons)C++20
0 / 100
2966 ms2102276 KiB
#include<iostream> #include<algorithm> #include <vector> #include<cmath> using namespace std; const int MAX_N=5100;//4e5+5; const int LOG=20; const long long INF=(1LL<<62); vector<int>wg[MAX_N]; vector<int>lg[MAX_N]; int _s[MAX_N]; int _p[MAX_N]; int _w[MAX_N]; int _l[MAX_N]; int _n; int wparent[MAX_N][LOG]; int lparent[MAX_N][LOG]; int wdep[MAX_N]; int ldep[MAX_N]; long long wdepth[MAX_N]; long long ldepth[MAX_N]; long long wmax[MAX_N][LOG]; long long lmin[MAX_N][LOG]; int depthtocycle[MAX_N]; vector<vector<int>>cycles; vector<vector<long long>>cyclemin[LOG]; int posincycle[MAX_N]; int whichcycle[MAX_N]; int cyclecnt; bool used[MAX_N]; void ldfs(int u) { used[u]=1; for(int j=1;j<LOG;j++) { lparent[u][j]=lparent[lparent[u][j-1]][j-1]; lmin[u][j]=min(lmin[u][j-1],lmin[lparent[u][j-1]][j-1]); } for(int v:lg[u]) { if(used[v])continue; depthtocycle[v]=depthtocycle[u]+(posincycle[v]!=-1); ldep[v]=ldep[u]+1; ldepth[v]=ldepth[u]+_p[v]; lparent[v][0]=u; lmin[v][0]=_s[v]+ldepth[v]; ldfs(v); } } void wdfs(int u) { for(int j=1;j<LOG;j++) { wparent[u][j]=wparent[wparent[u][j-1]][j-1]; wmax[u][j]=max(wmax[u][j-1],wmax[wparent[u][j-1]][j-1]); } for(int v:wg[u]) { wdep[v]=wdep[u]+1; wdepth[v]=wdepth[u]+_s[v]; wparent[v][0]=u; wmax[v][0]=_s[v]+wdepth[v]; wdfs(v); } } bool counted[MAX_N]; int findcycledfs(int u) { counted[u]=1; for(int v:lg[u]) { if(counted[v]) { return v; } int res=findcycledfs(v); if(res!=-1)return res; } return -1; } int lg2[2*MAX_N]; long long range(int cyclenum,int l,int r) { return (-(cyclemin[0][cyclenum][r]-_s[cycles[cyclenum][r]]))+(cyclemin[0][cyclenum][l]-_s[cycles[cyclenum][l]]); } long long query(int cyclenum,int l,int r) { int sz=r-l+1; int k=lg2[k]; int pos; if(cyclemin[k][cyclenum][l]<cyclemin[k][cyclenum][r-(1<<k)+1]) { return cyclemin[k][cyclenum][l]; } return cyclemin[k][cyclenum][r-(1<<k)+1]; } void solvecomponent(int u) { cyclecnt++; u=findcycledfs(u); vector<int>cycle; cycle.push_back(u); int v=_l[u]; while(v!=u) { cycle.push_back(v); v=_l[v]; } int sz=cycle.size(); for(int i=0;i<sz;i++) { cycle.push_back(cycle[i]); } cycles.push_back(cycle); long long cur=0; cyclemin[0].emplace_back(); cyclemin[0][cyclecnt-1].resize(cycle.size()); for(int i=0;i<cycle.size();i++) { if(posincycle[cycle[i]]==-1) { whichcycle[cycle[i]]=cyclecnt-1; posincycle[cycle[i]]=i; } cyclemin[0][cyclecnt-1][i]=_s[cycle[i]]-cur; cur+=_p[cycle[i]]; } for(int j=1;j<LOG;j++) { cyclemin[j].emplace_back(); cyclemin[j][cyclecnt-1].resize(cycle.size()); for(int i=0;i+(1<<j)-1<cycle.size();i++) { if(cyclemin[j-1][cyclecnt-1][i]<cyclemin[j-1][cyclecnt-1][i+(1<<(j-1))]) { cyclemin[j][cyclecnt-1][i]=cyclemin[j-1][cyclecnt-1][i]; } else { cyclemin[j][cyclecnt-1][i]=cyclemin[j-1][cyclecnt-1][i+(1<<(j-1))]; } } } ldfs(u); } void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) { _n=N; for(int i=1;i<=2*_n;i++) { lg2[i]=(int)log2(i); } for(int i=1;i<=_n;i++) { W[i-1]++;L[i-1]++; _s[i]=S[i-1]; _p[i]=P[i-1]; _w[i]=W[i-1]; _l[i]=L[i-1]; wg[_w[i]].push_back(i); lg[_l[i]].push_back(i); lg[i].push_back(_l[i]); posincycle[i]=-1; } wdfs(_n+1); for(int i=1;i<=_n;i++) { if(!used[i]) { solvecomponent(i); } } } void firstwin(int&x,long long&cur) { for(int j=LOG-1;j>=0;j--) { if(ldep[x]-(1<<j)<depthtocycle[x])continue; if(lmin[x][j]>cur+ldepth[x]) { cur+=ldepth[x]; x=lparent[x][j]; cur-=ldepth[x]; } } if(cur>=_s[x])return; int cyclenum=whichcycle[x]; int pos=posincycle[x]; long long mi=query(cyclenum,pos,pos+cycles[cyclenum].size()/2-1); if(cur<mi) { long long sum=range(cyclenum,pos,pos+cycles[cyclenum].size()/2); long long times=(mi-cur+sum-1)/sum; cur+=times*sum; } int ending=pos+cycles[cyclenum].size()/2-1; for(int j=LOG-1;j>=0;j--) { if(pos+(1<<j)>ending)continue; if(cyclemin[j][cyclenum][pos]>(cyclemin[0][cyclenum][pos]-_s[cycles[cyclenum][pos]]+cur)) { cur+=range(cyclenum,pos,pos+(1<<j)); pos+=(1<<j); } } x=cycles[cyclenum][pos]; } void firstlose(int&x,long long&cur) { for(int j=LOG-1;j>=0;j--) { if(wdep[x]-(1<<j)<0)continue; if(wmax[x][j]<=cur+wdepth[x]) { cur+=wdepth[x]; x=wparent[x][j]; cur-=wdepth[x]; } } } long long simulate(int x, int z) { long long cur=z; x++; while(x!=_n+1) { if(cur<_s[x]) { firstwin(x,cur); } else { firstlose(x,cur); } } return cur; }
#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...