Submission #943775

#	Time	Username	Problem	Language	Result	Execution time	Memory
943775		Pyqe	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	4979 ms	649052 KiB

dungeons

#include <bits/stdc++.h>
#include "dungeons.h"

using namespace std;

#define mp make_pair
#define fr first
#define sc second

const long long mm=24,inf=1e18;
long long n,nv,nn,a[400069],a2[400069],pr[400069],pr2[400069],ca[mm+1][400069],cpr[mm+1][400069],cmn[mm+1][400069],vi[400069],ex[400069],bl[mm+1][400069],dh[400069],wg[mm+1][400069],mna[mm+1][400069],cywg[mm+1][400069],cymn[mm+1][400069];
vector<long long> al[400069];
bitset<400069> spc;

void dfs(long long cr,long long x,long long sr)
{
	long long i,sz=al[x].size(),l,l2,l3;
	
	l=cpr[cr][x]*(x!=sr);
	l2=bl[cr][l];
	l3=bl[cr][l2];
	if(l&&l2&&l3&&dh[l2]-dh[l3]==dh[l]-dh[l2])
	{
		bl[cr][x]=l3;
		wg[cr][x]=ca[cr][x]+wg[cr][l]+wg[cr][l2];
		mna[cr][x]=min({cmn[cr][x],mna[cr][l]-ca[cr][x],mna[cr][l2]-wg[cr][l]-ca[cr][x]});
	}
	else
	{
		bl[cr][x]=l;
		wg[cr][x]=ca[cr][x];
		mna[cr][x]=cmn[cr][x];
	}
	for(i=0;i<sz;i++)
	{
		l=al[x][i];
		if(l==sr)
		{
			continue;
		}
		dh[l]=dh[x]+1;
		dfs(cr,l,sr);
	}
}

void init(int on,vector<int> oa,vector<int> oa2,vector<int> opr,vector<int> opr2)
{
	long long i,j,r,k,p,sm,mn;
	
	n=on;
	for(i=1;i<=n;i++)
	{
		a[i]=oa[i-1];
		a2[i]=oa2[i-1];
		pr[i]=opr[i-1]+1;
		pr2[i]=opr2[i-1]+1;
	}
	pr[n+1]=n+1;
	pr2[n+1]=n+1;
	for(i=0;i<=mm;i++)
	{
		for(j=1;j<=n+1;j++)
		{
			if(a[j]<1ll<<i)
			{
				ca[i][j]=a[j];
				cpr[i][j]=pr[j];
				cmn[i][j]=inf;
			}
			else
			{
				ca[i][j]=a2[j];
				cpr[i][j]=pr2[j];
				cmn[i][j]=a[j];
			}
			al[j].clear();
			vi[j]=0;
		}
		spc.reset();
		for(j=1;j<=n+1;j++)
		{
			al[cpr[i][j]].push_back(j);
		}
		nv=0;
		for(j=1;j<=n+1;j++)
		{
			nv++;
			for(p=j;!vi[p];p=cpr[i][p])
			{
				vi[p]=nv;
			}
			if(vi[p]==nv)
			{
				nn=0;
				for(;!spc[p];p=cpr[i][p])
				{
					spc[p]=1;
					nn++;
					ex[nn]=p;
				}
				k=ex[nn];
				bl[i][k]=0;
				dh[k]=0;
				dfs(i,k,k);
				sm=0;
				mn=inf;
				for(r=nn;r;r--)
				{
					k=ex[r];
					sm+=ca[i][k];
					mn=min(mn-ca[i][k],cmn[i][k]);
				}
				k=ex[1];
				cywg[i][k]=sm;
				cymn[i][k]=mn;
			}
		}
	}
}

long long simulate(int x,int w)
{
	long long i,ww,ub,c;
	
	x++;
	ww=w;
	for(i=0;i<=mm;i++)
	{
		ub=(1ll<<i+1)-1;
		if(i==mm)
		{
			ub=inf;
		}
		for(;x!=n+1&&ww<=ub;)
		{
			for(;1;)
			{
				if(!bl[i][x])
				{
					break;
				}
				if(bl[i][x]!=n+1&&ww+wg[i][x]<=ub&&ww<mna[i][x])
				{
					ww+=wg[i][x];
					x=bl[i][x];
				}
				else if(cpr[i][x]!=n+1&&ww+ca[i][x]<=ub&&ww<cmn[i][x])
				{
					ww+=ca[i][x];
					x=cpr[i][x];
				}
				else
				{
					break;
				}
			}
			if(ww>=a[x])
			{
				ww+=a[x];
				x=pr[x];
			}
			else
			{
				ww+=a2[x];
				x=pr2[x];
			}
			if(x!=n+1&&ww<=ub)
			{
				c=max(min(ub,cymn[i][x])-ww,0ll)/cywg[i][x];
				ww+=cywg[i][x]*c;
			}
		}
	}
	return ww;
}

Compilation message (stderr)

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:129:13: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  129 |   ub=(1ll<<i+1)-1;
      |            ~^~

• Subtask 1: 11 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 11 / 11