#include "dungeons.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
const int A=25;
const int B=15;
typedef long long ll;
struct xe{
int to;
ll cost=0;
ll mx=0;
};
struct no{
xe as[A];
};
vector<vector<no> > f;
vector<int> s,p,w,l;
vector<int> bs;
int n;
void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L) {
n=N;
s=S;
p=P;
w=W;
l=L;
const int C=9e7+5;
for(int h=1,z=0;h<C;h*=B,z++){
bs.push_back(h);
f.push_back(vector<no>(n+1));
for(int i=0;i<n;i++){
if(h>=s[i]){
f[z][i].as[0].to=w[i];
f[z][i].as[0].cost=s[i];
f[z][i].as[0].mx=1e18;
}
else{
f[z][i].as[0].to=l[i];
f[z][i].as[0].cost=p[i];
f[z][i].as[0].mx=s[i];
}
}
for(int i=1;i<A;i++){
for(int j=0;j<n;j++){
auto a=f[z][j].as[i-1],b=f[z][f[z][j].as[i-1].to].as[i-1];
if(a.to==n){
f[z][j].as[i]=a;
}
else{
f[z][j].as[i].to=b.to;
f[z][j].as[i].cost=a.cost+b.cost;
f[z][j].as[i].mx=min(a.mx,b.mx-a.cost);
}
}
}
}
bs.push_back(8*(9e7+5));
return;
}
ll simulate(int x, int Z) {
long long z=Z;
for(int j=0;j<f.size();j++){
while(z<bs[j+1]){
for(int i=A-1;i>=0;i--){
if(z<f[j][x].as[i].mx){
z+=f[j][x].as[i].cost;
x=f[j][x].as[i].to;
if(x==n){
return z;
}
}
}
if(z>=s[x]){
z+=s[x];
x=w[x];
}
else{
z+=p[x];
x=l[x];
}
if(x==n){
return z;
}
}
}
return z;
}
Compilation message
dungeons.cpp: In function 'll simulate(int, int)':
dungeons.cpp:65:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<no> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int j=0;j<f.size();j++){
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
5 ms |
8528 KB |
Output is correct |
4 |
Correct |
188 ms |
208096 KB |
Output is correct |
5 |
Correct |
5 ms |
8532 KB |
Output is correct |
6 |
Correct |
173 ms |
208044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4436 KB |
Output is correct |
2 |
Correct |
2422 ms |
1663660 KB |
Output is correct |
3 |
Correct |
2413 ms |
1663720 KB |
Output is correct |
4 |
Correct |
2319 ms |
1663904 KB |
Output is correct |
5 |
Correct |
2244 ms |
1664000 KB |
Output is correct |
6 |
Correct |
2424 ms |
1664160 KB |
Output is correct |
7 |
Correct |
2313 ms |
1664208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4436 KB |
Output is correct |
2 |
Correct |
231 ms |
209696 KB |
Output is correct |
3 |
Correct |
239 ms |
209364 KB |
Output is correct |
4 |
Correct |
221 ms |
209380 KB |
Output is correct |
5 |
Correct |
218 ms |
209236 KB |
Output is correct |
6 |
Correct |
263 ms |
209404 KB |
Output is correct |
7 |
Correct |
211 ms |
209360 KB |
Output is correct |
8 |
Correct |
232 ms |
209376 KB |
Output is correct |
9 |
Correct |
194 ms |
209384 KB |
Output is correct |
10 |
Correct |
195 ms |
209324 KB |
Output is correct |
11 |
Correct |
226 ms |
209368 KB |
Output is correct |
12 |
Correct |
264 ms |
209484 KB |
Output is correct |
13 |
Correct |
274 ms |
209340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4436 KB |
Output is correct |
2 |
Correct |
231 ms |
209696 KB |
Output is correct |
3 |
Correct |
239 ms |
209364 KB |
Output is correct |
4 |
Correct |
221 ms |
209380 KB |
Output is correct |
5 |
Correct |
218 ms |
209236 KB |
Output is correct |
6 |
Correct |
263 ms |
209404 KB |
Output is correct |
7 |
Correct |
211 ms |
209360 KB |
Output is correct |
8 |
Correct |
232 ms |
209376 KB |
Output is correct |
9 |
Correct |
194 ms |
209384 KB |
Output is correct |
10 |
Correct |
195 ms |
209324 KB |
Output is correct |
11 |
Correct |
226 ms |
209368 KB |
Output is correct |
12 |
Correct |
264 ms |
209484 KB |
Output is correct |
13 |
Correct |
274 ms |
209340 KB |
Output is correct |
14 |
Correct |
4 ms |
4436 KB |
Output is correct |
15 |
Correct |
220 ms |
209520 KB |
Output is correct |
16 |
Correct |
253 ms |
209480 KB |
Output is correct |
17 |
Correct |
210 ms |
209292 KB |
Output is correct |
18 |
Correct |
205 ms |
209464 KB |
Output is correct |
19 |
Correct |
228 ms |
209436 KB |
Output is correct |
20 |
Correct |
240 ms |
209148 KB |
Output is correct |
21 |
Correct |
214 ms |
209476 KB |
Output is correct |
22 |
Correct |
278 ms |
209508 KB |
Output is correct |
23 |
Correct |
233 ms |
209588 KB |
Output is correct |
24 |
Correct |
435 ms |
209540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4436 KB |
Output is correct |
2 |
Correct |
231 ms |
209696 KB |
Output is correct |
3 |
Correct |
239 ms |
209364 KB |
Output is correct |
4 |
Correct |
221 ms |
209380 KB |
Output is correct |
5 |
Correct |
218 ms |
209236 KB |
Output is correct |
6 |
Correct |
263 ms |
209404 KB |
Output is correct |
7 |
Correct |
211 ms |
209360 KB |
Output is correct |
8 |
Correct |
232 ms |
209376 KB |
Output is correct |
9 |
Correct |
194 ms |
209384 KB |
Output is correct |
10 |
Correct |
195 ms |
209324 KB |
Output is correct |
11 |
Correct |
226 ms |
209368 KB |
Output is correct |
12 |
Correct |
264 ms |
209484 KB |
Output is correct |
13 |
Correct |
274 ms |
209340 KB |
Output is correct |
14 |
Correct |
4 ms |
4436 KB |
Output is correct |
15 |
Correct |
220 ms |
209520 KB |
Output is correct |
16 |
Correct |
253 ms |
209480 KB |
Output is correct |
17 |
Correct |
210 ms |
209292 KB |
Output is correct |
18 |
Correct |
205 ms |
209464 KB |
Output is correct |
19 |
Correct |
228 ms |
209436 KB |
Output is correct |
20 |
Correct |
240 ms |
209148 KB |
Output is correct |
21 |
Correct |
214 ms |
209476 KB |
Output is correct |
22 |
Correct |
278 ms |
209508 KB |
Output is correct |
23 |
Correct |
233 ms |
209588 KB |
Output is correct |
24 |
Correct |
435 ms |
209540 KB |
Output is correct |
25 |
Correct |
213 ms |
208820 KB |
Output is correct |
26 |
Correct |
210 ms |
209384 KB |
Output is correct |
27 |
Correct |
212 ms |
209476 KB |
Output is correct |
28 |
Correct |
243 ms |
209588 KB |
Output is correct |
29 |
Correct |
223 ms |
209352 KB |
Output is correct |
30 |
Correct |
236 ms |
209616 KB |
Output is correct |
31 |
Correct |
250 ms |
209336 KB |
Output is correct |
32 |
Correct |
226 ms |
209524 KB |
Output is correct |
33 |
Correct |
485 ms |
209612 KB |
Output is correct |
34 |
Correct |
1209 ms |
209684 KB |
Output is correct |
35 |
Correct |
554 ms |
209572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4436 KB |
Output is correct |
2 |
Correct |
2422 ms |
1663660 KB |
Output is correct |
3 |
Correct |
2413 ms |
1663720 KB |
Output is correct |
4 |
Correct |
2319 ms |
1663904 KB |
Output is correct |
5 |
Correct |
2244 ms |
1664000 KB |
Output is correct |
6 |
Correct |
2424 ms |
1664160 KB |
Output is correct |
7 |
Correct |
2313 ms |
1664208 KB |
Output is correct |
8 |
Correct |
4 ms |
4436 KB |
Output is correct |
9 |
Correct |
231 ms |
209696 KB |
Output is correct |
10 |
Correct |
239 ms |
209364 KB |
Output is correct |
11 |
Correct |
221 ms |
209380 KB |
Output is correct |
12 |
Correct |
218 ms |
209236 KB |
Output is correct |
13 |
Correct |
263 ms |
209404 KB |
Output is correct |
14 |
Correct |
211 ms |
209360 KB |
Output is correct |
15 |
Correct |
232 ms |
209376 KB |
Output is correct |
16 |
Correct |
194 ms |
209384 KB |
Output is correct |
17 |
Correct |
195 ms |
209324 KB |
Output is correct |
18 |
Correct |
226 ms |
209368 KB |
Output is correct |
19 |
Correct |
264 ms |
209484 KB |
Output is correct |
20 |
Correct |
274 ms |
209340 KB |
Output is correct |
21 |
Correct |
4 ms |
4436 KB |
Output is correct |
22 |
Correct |
220 ms |
209520 KB |
Output is correct |
23 |
Correct |
253 ms |
209480 KB |
Output is correct |
24 |
Correct |
210 ms |
209292 KB |
Output is correct |
25 |
Correct |
205 ms |
209464 KB |
Output is correct |
26 |
Correct |
228 ms |
209436 KB |
Output is correct |
27 |
Correct |
240 ms |
209148 KB |
Output is correct |
28 |
Correct |
214 ms |
209476 KB |
Output is correct |
29 |
Correct |
278 ms |
209508 KB |
Output is correct |
30 |
Correct |
233 ms |
209588 KB |
Output is correct |
31 |
Correct |
435 ms |
209540 KB |
Output is correct |
32 |
Correct |
213 ms |
208820 KB |
Output is correct |
33 |
Correct |
210 ms |
209384 KB |
Output is correct |
34 |
Correct |
212 ms |
209476 KB |
Output is correct |
35 |
Correct |
243 ms |
209588 KB |
Output is correct |
36 |
Correct |
223 ms |
209352 KB |
Output is correct |
37 |
Correct |
236 ms |
209616 KB |
Output is correct |
38 |
Correct |
250 ms |
209336 KB |
Output is correct |
39 |
Correct |
226 ms |
209524 KB |
Output is correct |
40 |
Correct |
485 ms |
209612 KB |
Output is correct |
41 |
Correct |
1209 ms |
209684 KB |
Output is correct |
42 |
Correct |
554 ms |
209572 KB |
Output is correct |
43 |
Correct |
1 ms |
212 KB |
Output is correct |
44 |
Correct |
4 ms |
4436 KB |
Output is correct |
45 |
Correct |
2277 ms |
1665280 KB |
Output is correct |
46 |
Correct |
2071 ms |
1665568 KB |
Output is correct |
47 |
Correct |
2031 ms |
1665732 KB |
Output is correct |
48 |
Correct |
2189 ms |
1665648 KB |
Output is correct |
49 |
Correct |
2493 ms |
1665540 KB |
Output is correct |
50 |
Correct |
2336 ms |
1665532 KB |
Output is correct |
51 |
Correct |
2084 ms |
1665472 KB |
Output is correct |
52 |
Correct |
2318 ms |
1665144 KB |
Output is correct |
53 |
Correct |
2665 ms |
1665648 KB |
Output is correct |
54 |
Correct |
2915 ms |
1665172 KB |
Output is correct |
55 |
Correct |
3538 ms |
1665052 KB |
Output is correct |
56 |
Correct |
3003 ms |
1665132 KB |
Output is correct |
57 |
Correct |
2716 ms |
1665000 KB |
Output is correct |
58 |
Correct |
2897 ms |
1664972 KB |
Output is correct |
59 |
Correct |
2761 ms |
1664616 KB |
Output is correct |
60 |
Correct |
4239 ms |
1663892 KB |
Output is correct |
61 |
Correct |
4176 ms |
1663616 KB |
Output is correct |