#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=10;
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++){
| ~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
6 ms |
9832 KB |
Output is correct |
4 |
Correct |
235 ms |
238508 KB |
Output is correct |
5 |
Correct |
7 ms |
9812 KB |
Output is correct |
6 |
Correct |
236 ms |
238404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
5048 KB |
Output is correct |
2 |
Correct |
2826 ms |
1905448 KB |
Output is correct |
3 |
Correct |
2802 ms |
1905444 KB |
Output is correct |
4 |
Correct |
2574 ms |
1906864 KB |
Output is correct |
5 |
Correct |
2180 ms |
1906992 KB |
Output is correct |
6 |
Correct |
2458 ms |
1905364 KB |
Output is correct |
7 |
Correct |
2662 ms |
1903656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
265 ms |
238232 KB |
Output is correct |
3 |
Correct |
235 ms |
238156 KB |
Output is correct |
4 |
Correct |
227 ms |
238432 KB |
Output is correct |
5 |
Correct |
244 ms |
238228 KB |
Output is correct |
6 |
Correct |
247 ms |
238200 KB |
Output is correct |
7 |
Correct |
253 ms |
238248 KB |
Output is correct |
8 |
Correct |
229 ms |
238272 KB |
Output is correct |
9 |
Correct |
222 ms |
238156 KB |
Output is correct |
10 |
Correct |
230 ms |
238288 KB |
Output is correct |
11 |
Correct |
270 ms |
238180 KB |
Output is correct |
12 |
Correct |
361 ms |
238236 KB |
Output is correct |
13 |
Correct |
342 ms |
238164 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
265 ms |
238232 KB |
Output is correct |
3 |
Correct |
235 ms |
238156 KB |
Output is correct |
4 |
Correct |
227 ms |
238432 KB |
Output is correct |
5 |
Correct |
244 ms |
238228 KB |
Output is correct |
6 |
Correct |
247 ms |
238200 KB |
Output is correct |
7 |
Correct |
253 ms |
238248 KB |
Output is correct |
8 |
Correct |
229 ms |
238272 KB |
Output is correct |
9 |
Correct |
222 ms |
238156 KB |
Output is correct |
10 |
Correct |
230 ms |
238288 KB |
Output is correct |
11 |
Correct |
270 ms |
238180 KB |
Output is correct |
12 |
Correct |
361 ms |
238236 KB |
Output is correct |
13 |
Correct |
342 ms |
238164 KB |
Output is correct |
14 |
Correct |
3 ms |
5076 KB |
Output is correct |
15 |
Correct |
232 ms |
238212 KB |
Output is correct |
16 |
Correct |
240 ms |
238192 KB |
Output is correct |
17 |
Correct |
249 ms |
238292 KB |
Output is correct |
18 |
Correct |
234 ms |
238264 KB |
Output is correct |
19 |
Correct |
251 ms |
238288 KB |
Output is correct |
20 |
Correct |
257 ms |
238276 KB |
Output is correct |
21 |
Correct |
287 ms |
238232 KB |
Output is correct |
22 |
Correct |
250 ms |
238288 KB |
Output is correct |
23 |
Correct |
256 ms |
238240 KB |
Output is correct |
24 |
Correct |
364 ms |
238288 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
265 ms |
238232 KB |
Output is correct |
3 |
Correct |
235 ms |
238156 KB |
Output is correct |
4 |
Correct |
227 ms |
238432 KB |
Output is correct |
5 |
Correct |
244 ms |
238228 KB |
Output is correct |
6 |
Correct |
247 ms |
238200 KB |
Output is correct |
7 |
Correct |
253 ms |
238248 KB |
Output is correct |
8 |
Correct |
229 ms |
238272 KB |
Output is correct |
9 |
Correct |
222 ms |
238156 KB |
Output is correct |
10 |
Correct |
230 ms |
238288 KB |
Output is correct |
11 |
Correct |
270 ms |
238180 KB |
Output is correct |
12 |
Correct |
361 ms |
238236 KB |
Output is correct |
13 |
Correct |
342 ms |
238164 KB |
Output is correct |
14 |
Correct |
3 ms |
5076 KB |
Output is correct |
15 |
Correct |
232 ms |
238212 KB |
Output is correct |
16 |
Correct |
240 ms |
238192 KB |
Output is correct |
17 |
Correct |
249 ms |
238292 KB |
Output is correct |
18 |
Correct |
234 ms |
238264 KB |
Output is correct |
19 |
Correct |
251 ms |
238288 KB |
Output is correct |
20 |
Correct |
257 ms |
238276 KB |
Output is correct |
21 |
Correct |
287 ms |
238232 KB |
Output is correct |
22 |
Correct |
250 ms |
238288 KB |
Output is correct |
23 |
Correct |
256 ms |
238240 KB |
Output is correct |
24 |
Correct |
364 ms |
238288 KB |
Output is correct |
25 |
Correct |
244 ms |
237544 KB |
Output is correct |
26 |
Correct |
255 ms |
238244 KB |
Output is correct |
27 |
Correct |
227 ms |
238224 KB |
Output is correct |
28 |
Correct |
238 ms |
238340 KB |
Output is correct |
29 |
Correct |
315 ms |
238172 KB |
Output is correct |
30 |
Correct |
266 ms |
238272 KB |
Output is correct |
31 |
Correct |
279 ms |
238304 KB |
Output is correct |
32 |
Correct |
324 ms |
238224 KB |
Output is correct |
33 |
Correct |
578 ms |
238136 KB |
Output is correct |
34 |
Correct |
1041 ms |
238080 KB |
Output is correct |
35 |
Correct |
392 ms |
238284 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
5048 KB |
Output is correct |
2 |
Correct |
2826 ms |
1905448 KB |
Output is correct |
3 |
Correct |
2802 ms |
1905444 KB |
Output is correct |
4 |
Correct |
2574 ms |
1906864 KB |
Output is correct |
5 |
Correct |
2180 ms |
1906992 KB |
Output is correct |
6 |
Correct |
2458 ms |
1905364 KB |
Output is correct |
7 |
Correct |
2662 ms |
1903656 KB |
Output is correct |
8 |
Correct |
3 ms |
5076 KB |
Output is correct |
9 |
Correct |
265 ms |
238232 KB |
Output is correct |
10 |
Correct |
235 ms |
238156 KB |
Output is correct |
11 |
Correct |
227 ms |
238432 KB |
Output is correct |
12 |
Correct |
244 ms |
238228 KB |
Output is correct |
13 |
Correct |
247 ms |
238200 KB |
Output is correct |
14 |
Correct |
253 ms |
238248 KB |
Output is correct |
15 |
Correct |
229 ms |
238272 KB |
Output is correct |
16 |
Correct |
222 ms |
238156 KB |
Output is correct |
17 |
Correct |
230 ms |
238288 KB |
Output is correct |
18 |
Correct |
270 ms |
238180 KB |
Output is correct |
19 |
Correct |
361 ms |
238236 KB |
Output is correct |
20 |
Correct |
342 ms |
238164 KB |
Output is correct |
21 |
Correct |
3 ms |
5076 KB |
Output is correct |
22 |
Correct |
232 ms |
238212 KB |
Output is correct |
23 |
Correct |
240 ms |
238192 KB |
Output is correct |
24 |
Correct |
249 ms |
238292 KB |
Output is correct |
25 |
Correct |
234 ms |
238264 KB |
Output is correct |
26 |
Correct |
251 ms |
238288 KB |
Output is correct |
27 |
Correct |
257 ms |
238276 KB |
Output is correct |
28 |
Correct |
287 ms |
238232 KB |
Output is correct |
29 |
Correct |
250 ms |
238288 KB |
Output is correct |
30 |
Correct |
256 ms |
238240 KB |
Output is correct |
31 |
Correct |
364 ms |
238288 KB |
Output is correct |
32 |
Correct |
244 ms |
237544 KB |
Output is correct |
33 |
Correct |
255 ms |
238244 KB |
Output is correct |
34 |
Correct |
227 ms |
238224 KB |
Output is correct |
35 |
Correct |
238 ms |
238340 KB |
Output is correct |
36 |
Correct |
315 ms |
238172 KB |
Output is correct |
37 |
Correct |
266 ms |
238272 KB |
Output is correct |
38 |
Correct |
279 ms |
238304 KB |
Output is correct |
39 |
Correct |
324 ms |
238224 KB |
Output is correct |
40 |
Correct |
578 ms |
238136 KB |
Output is correct |
41 |
Correct |
1041 ms |
238080 KB |
Output is correct |
42 |
Correct |
392 ms |
238284 KB |
Output is correct |
43 |
Correct |
1 ms |
212 KB |
Output is correct |
44 |
Correct |
4 ms |
5076 KB |
Output is correct |
45 |
Correct |
2390 ms |
1910148 KB |
Output is correct |
46 |
Correct |
2353 ms |
1905576 KB |
Output is correct |
47 |
Correct |
2185 ms |
1906144 KB |
Output is correct |
48 |
Correct |
2286 ms |
1908072 KB |
Output is correct |
49 |
Correct |
2414 ms |
1910200 KB |
Output is correct |
50 |
Correct |
2589 ms |
1907804 KB |
Output is correct |
51 |
Correct |
2709 ms |
1908224 KB |
Output is correct |
52 |
Correct |
2724 ms |
1905832 KB |
Output is correct |
53 |
Correct |
3318 ms |
1906572 KB |
Output is correct |
54 |
Correct |
3427 ms |
1907660 KB |
Output is correct |
55 |
Correct |
4735 ms |
1906692 KB |
Output is correct |
56 |
Correct |
3069 ms |
1907304 KB |
Output is correct |
57 |
Correct |
3055 ms |
1907500 KB |
Output is correct |
58 |
Correct |
3444 ms |
1907392 KB |
Output is correct |
59 |
Correct |
3246 ms |
1907508 KB |
Output is correct |
60 |
Correct |
4135 ms |
1906796 KB |
Output is correct |
61 |
Correct |
3786 ms |
1906744 KB |
Output is correct |