#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
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;
| ~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
177936 KB |
Output is correct |
2 |
Correct |
30 ms |
210636 KB |
Output is correct |
3 |
Correct |
28 ms |
212060 KB |
Output is correct |
4 |
Correct |
136 ms |
251708 KB |
Output is correct |
5 |
Correct |
28 ms |
216144 KB |
Output is correct |
6 |
Correct |
127 ms |
251472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
211548 KB |
Output is correct |
2 |
Correct |
1483 ms |
597312 KB |
Output is correct |
3 |
Correct |
1519 ms |
615312 KB |
Output is correct |
4 |
Correct |
1813 ms |
616824 KB |
Output is correct |
5 |
Correct |
2314 ms |
576816 KB |
Output is correct |
6 |
Correct |
2391 ms |
597576 KB |
Output is correct |
7 |
Correct |
1434 ms |
607164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
211536 KB |
Output is correct |
2 |
Correct |
161 ms |
254844 KB |
Output is correct |
3 |
Correct |
140 ms |
256580 KB |
Output is correct |
4 |
Correct |
130 ms |
256596 KB |
Output is correct |
5 |
Correct |
152 ms |
256836 KB |
Output is correct |
6 |
Correct |
305 ms |
253268 KB |
Output is correct |
7 |
Correct |
301 ms |
253008 KB |
Output is correct |
8 |
Correct |
305 ms |
256340 KB |
Output is correct |
9 |
Correct |
154 ms |
251732 KB |
Output is correct |
10 |
Correct |
270 ms |
256340 KB |
Output is correct |
11 |
Correct |
485 ms |
258424 KB |
Output is correct |
12 |
Correct |
1930 ms |
257928 KB |
Output is correct |
13 |
Correct |
940 ms |
259708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
211536 KB |
Output is correct |
2 |
Correct |
161 ms |
254844 KB |
Output is correct |
3 |
Correct |
140 ms |
256580 KB |
Output is correct |
4 |
Correct |
130 ms |
256596 KB |
Output is correct |
5 |
Correct |
152 ms |
256836 KB |
Output is correct |
6 |
Correct |
305 ms |
253268 KB |
Output is correct |
7 |
Correct |
301 ms |
253008 KB |
Output is correct |
8 |
Correct |
305 ms |
256340 KB |
Output is correct |
9 |
Correct |
154 ms |
251732 KB |
Output is correct |
10 |
Correct |
270 ms |
256340 KB |
Output is correct |
11 |
Correct |
485 ms |
258424 KB |
Output is correct |
12 |
Correct |
1930 ms |
257928 KB |
Output is correct |
13 |
Correct |
940 ms |
259708 KB |
Output is correct |
14 |
Correct |
26 ms |
211548 KB |
Output is correct |
15 |
Correct |
163 ms |
290900 KB |
Output is correct |
16 |
Correct |
160 ms |
289344 KB |
Output is correct |
17 |
Correct |
173 ms |
289820 KB |
Output is correct |
18 |
Correct |
187 ms |
290004 KB |
Output is correct |
19 |
Correct |
285 ms |
290880 KB |
Output is correct |
20 |
Correct |
274 ms |
288896 KB |
Output is correct |
21 |
Correct |
307 ms |
287312 KB |
Output is correct |
22 |
Correct |
410 ms |
288888 KB |
Output is correct |
23 |
Correct |
886 ms |
290128 KB |
Output is correct |
24 |
Correct |
960 ms |
291476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
211536 KB |
Output is correct |
2 |
Correct |
161 ms |
254844 KB |
Output is correct |
3 |
Correct |
140 ms |
256580 KB |
Output is correct |
4 |
Correct |
130 ms |
256596 KB |
Output is correct |
5 |
Correct |
152 ms |
256836 KB |
Output is correct |
6 |
Correct |
305 ms |
253268 KB |
Output is correct |
7 |
Correct |
301 ms |
253008 KB |
Output is correct |
8 |
Correct |
305 ms |
256340 KB |
Output is correct |
9 |
Correct |
154 ms |
251732 KB |
Output is correct |
10 |
Correct |
270 ms |
256340 KB |
Output is correct |
11 |
Correct |
485 ms |
258424 KB |
Output is correct |
12 |
Correct |
1930 ms |
257928 KB |
Output is correct |
13 |
Correct |
940 ms |
259708 KB |
Output is correct |
14 |
Correct |
26 ms |
211548 KB |
Output is correct |
15 |
Correct |
163 ms |
290900 KB |
Output is correct |
16 |
Correct |
160 ms |
289344 KB |
Output is correct |
17 |
Correct |
173 ms |
289820 KB |
Output is correct |
18 |
Correct |
187 ms |
290004 KB |
Output is correct |
19 |
Correct |
285 ms |
290880 KB |
Output is correct |
20 |
Correct |
274 ms |
288896 KB |
Output is correct |
21 |
Correct |
307 ms |
287312 KB |
Output is correct |
22 |
Correct |
410 ms |
288888 KB |
Output is correct |
23 |
Correct |
886 ms |
290128 KB |
Output is correct |
24 |
Correct |
960 ms |
291476 KB |
Output is correct |
25 |
Correct |
135 ms |
284708 KB |
Output is correct |
26 |
Correct |
156 ms |
289380 KB |
Output is correct |
27 |
Correct |
143 ms |
287312 KB |
Output is correct |
28 |
Correct |
142 ms |
287724 KB |
Output is correct |
29 |
Correct |
170 ms |
287808 KB |
Output is correct |
30 |
Correct |
284 ms |
289072 KB |
Output is correct |
31 |
Correct |
371 ms |
290900 KB |
Output is correct |
32 |
Correct |
552 ms |
288764 KB |
Output is correct |
33 |
Correct |
283 ms |
289404 KB |
Output is correct |
34 |
Correct |
533 ms |
281680 KB |
Output is correct |
35 |
Correct |
538 ms |
287692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
211548 KB |
Output is correct |
2 |
Correct |
1483 ms |
597312 KB |
Output is correct |
3 |
Correct |
1519 ms |
615312 KB |
Output is correct |
4 |
Correct |
1813 ms |
616824 KB |
Output is correct |
5 |
Correct |
2314 ms |
576816 KB |
Output is correct |
6 |
Correct |
2391 ms |
597576 KB |
Output is correct |
7 |
Correct |
1434 ms |
607164 KB |
Output is correct |
8 |
Correct |
25 ms |
211536 KB |
Output is correct |
9 |
Correct |
161 ms |
254844 KB |
Output is correct |
10 |
Correct |
140 ms |
256580 KB |
Output is correct |
11 |
Correct |
130 ms |
256596 KB |
Output is correct |
12 |
Correct |
152 ms |
256836 KB |
Output is correct |
13 |
Correct |
305 ms |
253268 KB |
Output is correct |
14 |
Correct |
301 ms |
253008 KB |
Output is correct |
15 |
Correct |
305 ms |
256340 KB |
Output is correct |
16 |
Correct |
154 ms |
251732 KB |
Output is correct |
17 |
Correct |
270 ms |
256340 KB |
Output is correct |
18 |
Correct |
485 ms |
258424 KB |
Output is correct |
19 |
Correct |
1930 ms |
257928 KB |
Output is correct |
20 |
Correct |
940 ms |
259708 KB |
Output is correct |
21 |
Correct |
26 ms |
211548 KB |
Output is correct |
22 |
Correct |
163 ms |
290900 KB |
Output is correct |
23 |
Correct |
160 ms |
289344 KB |
Output is correct |
24 |
Correct |
173 ms |
289820 KB |
Output is correct |
25 |
Correct |
187 ms |
290004 KB |
Output is correct |
26 |
Correct |
285 ms |
290880 KB |
Output is correct |
27 |
Correct |
274 ms |
288896 KB |
Output is correct |
28 |
Correct |
307 ms |
287312 KB |
Output is correct |
29 |
Correct |
410 ms |
288888 KB |
Output is correct |
30 |
Correct |
886 ms |
290128 KB |
Output is correct |
31 |
Correct |
960 ms |
291476 KB |
Output is correct |
32 |
Correct |
135 ms |
284708 KB |
Output is correct |
33 |
Correct |
156 ms |
289380 KB |
Output is correct |
34 |
Correct |
143 ms |
287312 KB |
Output is correct |
35 |
Correct |
142 ms |
287724 KB |
Output is correct |
36 |
Correct |
170 ms |
287808 KB |
Output is correct |
37 |
Correct |
284 ms |
289072 KB |
Output is correct |
38 |
Correct |
371 ms |
290900 KB |
Output is correct |
39 |
Correct |
552 ms |
288764 KB |
Output is correct |
40 |
Correct |
283 ms |
289404 KB |
Output is correct |
41 |
Correct |
533 ms |
281680 KB |
Output is correct |
42 |
Correct |
538 ms |
287692 KB |
Output is correct |
43 |
Correct |
26 ms |
249428 KB |
Output is correct |
44 |
Correct |
29 ms |
250524 KB |
Output is correct |
45 |
Correct |
2772 ms |
621168 KB |
Output is correct |
46 |
Correct |
2288 ms |
600148 KB |
Output is correct |
47 |
Correct |
2301 ms |
600404 KB |
Output is correct |
48 |
Correct |
2113 ms |
637348 KB |
Output is correct |
49 |
Correct |
2700 ms |
616996 KB |
Output is correct |
50 |
Correct |
1883 ms |
626452 KB |
Output is correct |
51 |
Correct |
2104 ms |
633196 KB |
Output is correct |
52 |
Correct |
1935 ms |
628548 KB |
Output is correct |
53 |
Correct |
4477 ms |
645680 KB |
Output is correct |
54 |
Correct |
1429 ms |
611496 KB |
Output is correct |
55 |
Correct |
1818 ms |
593572 KB |
Output is correct |
56 |
Correct |
4056 ms |
645108 KB |
Output is correct |
57 |
Correct |
3932 ms |
649052 KB |
Output is correct |
58 |
Correct |
4054 ms |
640972 KB |
Output is correct |
59 |
Correct |
4242 ms |
641448 KB |
Output is correct |
60 |
Correct |
4979 ms |
619664 KB |
Output is correct |
61 |
Correct |
4873 ms |
640012 KB |
Output is correct |