#include "dungeons.h"
#include <bits/stdc++.h>
#define N 400005
#define M 50005
#define K 30
#define X 10
using namespace std;
struct node{
int to;
long long val;
};
struct node2{
int to;
long long sum;
long long maxi;
};
node sp[M][X][K];
node2 sp2[N][K];
vector<int> numbers;
int sz;
int n;
bool subtask4 = 0;
bool subtask2 = 1;
vector<int> s,p,w,l;
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_;
for(int i = 0;i<n;i++){
subtask2 &= (s[i] == p[i]);
numbers.push_back(s[i]);
}
sort(numbers.begin(),numbers.end());
numbers.resize(unique(numbers.begin(),numbers.end())-numbers.begin());
sz = numbers.size();
if(sz <= 5 && n <= 50000)subtask4 = 1;
if(subtask4){
for(int x = 0;x<=sz;x++){
sp[n][x][0].to = n;
sp[n][x][0].val = 0;
for(int i = 0;i<n;i++){
int num = upper_bound(numbers.begin(),numbers.end(),s[i]) - numbers.begin();
if(num <= x){
sp[i][x][0].to = w[i];
sp[i][x][0].val = s[i];
}
else{
sp[i][x][0].to = l[i];
sp[i][x][0].val = p[i];
}
}
for(int j = 1;j<K;j++){
for(int i = 0;i<=n;i++){
sp[i][x][j].val = sp[i][x][j-1].val + sp[sp[i][x][j-1].to][x][j-1].val;
sp[i][x][j].to = sp[sp[i][x][j-1].to][x][j-1].to;
}
}
}
}
if(subtask2){
for(int i = 0;i<n;i++){
sp2[i][0].to = w[i];
sp2[i][0].sum = s[i];
sp2[i][0].maxi = s[i];
}
sp2[n][0].to = n;
sp2[n][0].sum = 0;
sp2[n][0].maxi = 0;
for(int j = 1;j<K;j++){
for(int i = 0;i<=n;i++){
sp2[i][j].to = sp2[sp2[i][j-1].to][j-1].to;
sp2[i][j].sum = sp2[i][j-1].sum + sp2[sp2[i][j-1].to][j-1].sum;
sp2[i][j].maxi = max(sp2[i][j-1].maxi,sp2[sp2[i][j-1].to][j-1].maxi - sp2[i][j-1].sum);
}
}
}
return;
}
long long simulate(int x, int z) {
long long pw = z;
int now = upper_bound(numbers.begin(),numbers.end(),pw) - numbers.begin();
if(subtask2){
while(x != n){
for(int i = K-1;i>=0;i--){
if(sp2[x][i].maxi <= pw){
pw += sp2[x][i].sum;
x = sp2[x][i].to;
}
}
if(x != n){
pw += p[x];
x = l[x];
}
}
return pw;
}
if(subtask4){
while(x != n){
//cout << now << " " << x << " " << pw << endl;
if(now == sz){
pw += sp[x][now][K-1].val;
x = sp[x][now][K-1].to;
assert(x == n);
}
else{
for(int i = K-1;i>=0;i--){
if(sp[x][now][i].val + pw < numbers[now]){
pw += sp[x][now][i].val;
x = sp[x][now][i].to;
}
}
pw += sp[x][now][0].val;
x = sp[x][now][0].to;
while(now != sz && pw >= numbers[now])
now++;
}
}
return pw;
}
while(x != n){
if(s[x] <= pw){
pw += s[x];
x = w[x];
}
else{
pw += p[x];
x = l[x];
}
}
return pw;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
20 ms |
3020 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
20 ms |
3024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
980 KB |
Output is correct |
2 |
Correct |
494 ms |
303268 KB |
Output is correct |
3 |
Correct |
459 ms |
303396 KB |
Output is correct |
4 |
Correct |
523 ms |
303380 KB |
Output is correct |
5 |
Correct |
449 ms |
303292 KB |
Output is correct |
6 |
Correct |
509 ms |
303388 KB |
Output is correct |
7 |
Correct |
533 ms |
303580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
170 ms |
238548 KB |
Output is correct |
3 |
Correct |
174 ms |
238532 KB |
Output is correct |
4 |
Correct |
159 ms |
238556 KB |
Output is correct |
5 |
Correct |
154 ms |
238524 KB |
Output is correct |
6 |
Correct |
168 ms |
238532 KB |
Output is correct |
7 |
Correct |
183 ms |
238584 KB |
Output is correct |
8 |
Correct |
168 ms |
238532 KB |
Output is correct |
9 |
Correct |
181 ms |
238508 KB |
Output is correct |
10 |
Correct |
155 ms |
238540 KB |
Output is correct |
11 |
Correct |
167 ms |
238500 KB |
Output is correct |
12 |
Correct |
249 ms |
238484 KB |
Output is correct |
13 |
Correct |
234 ms |
238612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
170 ms |
238548 KB |
Output is correct |
3 |
Correct |
174 ms |
238532 KB |
Output is correct |
4 |
Correct |
159 ms |
238556 KB |
Output is correct |
5 |
Correct |
154 ms |
238524 KB |
Output is correct |
6 |
Correct |
168 ms |
238532 KB |
Output is correct |
7 |
Correct |
183 ms |
238584 KB |
Output is correct |
8 |
Correct |
168 ms |
238532 KB |
Output is correct |
9 |
Correct |
181 ms |
238508 KB |
Output is correct |
10 |
Correct |
155 ms |
238540 KB |
Output is correct |
11 |
Correct |
167 ms |
238500 KB |
Output is correct |
12 |
Correct |
249 ms |
238484 KB |
Output is correct |
13 |
Correct |
234 ms |
238612 KB |
Output is correct |
14 |
Correct |
3 ms |
5076 KB |
Output is correct |
15 |
Correct |
211 ms |
238536 KB |
Output is correct |
16 |
Correct |
230 ms |
238568 KB |
Output is correct |
17 |
Correct |
241 ms |
238584 KB |
Output is correct |
18 |
Correct |
275 ms |
238536 KB |
Output is correct |
19 |
Correct |
284 ms |
238604 KB |
Output is correct |
20 |
Correct |
256 ms |
238604 KB |
Output is correct |
21 |
Correct |
256 ms |
238664 KB |
Output is correct |
22 |
Correct |
199 ms |
238584 KB |
Output is correct |
23 |
Correct |
271 ms |
238576 KB |
Output is correct |
24 |
Correct |
319 ms |
238600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
170 ms |
238548 KB |
Output is correct |
3 |
Correct |
174 ms |
238532 KB |
Output is correct |
4 |
Correct |
159 ms |
238556 KB |
Output is correct |
5 |
Correct |
154 ms |
238524 KB |
Output is correct |
6 |
Correct |
168 ms |
238532 KB |
Output is correct |
7 |
Correct |
183 ms |
238584 KB |
Output is correct |
8 |
Correct |
168 ms |
238532 KB |
Output is correct |
9 |
Correct |
181 ms |
238508 KB |
Output is correct |
10 |
Correct |
155 ms |
238540 KB |
Output is correct |
11 |
Correct |
167 ms |
238500 KB |
Output is correct |
12 |
Correct |
249 ms |
238484 KB |
Output is correct |
13 |
Correct |
234 ms |
238612 KB |
Output is correct |
14 |
Correct |
3 ms |
5076 KB |
Output is correct |
15 |
Correct |
211 ms |
238536 KB |
Output is correct |
16 |
Correct |
230 ms |
238568 KB |
Output is correct |
17 |
Correct |
241 ms |
238584 KB |
Output is correct |
18 |
Correct |
275 ms |
238536 KB |
Output is correct |
19 |
Correct |
284 ms |
238604 KB |
Output is correct |
20 |
Correct |
256 ms |
238604 KB |
Output is correct |
21 |
Correct |
256 ms |
238664 KB |
Output is correct |
22 |
Correct |
199 ms |
238584 KB |
Output is correct |
23 |
Correct |
271 ms |
238576 KB |
Output is correct |
24 |
Correct |
319 ms |
238600 KB |
Output is correct |
25 |
Correct |
22 ms |
3028 KB |
Output is correct |
26 |
Correct |
50 ms |
3796 KB |
Output is correct |
27 |
Correct |
49 ms |
3796 KB |
Output is correct |
28 |
Correct |
328 ms |
3812 KB |
Output is correct |
29 |
Correct |
45 ms |
3796 KB |
Output is correct |
30 |
Execution timed out |
7015 ms |
3792 KB |
Time limit exceeded |
31 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
980 KB |
Output is correct |
2 |
Correct |
494 ms |
303268 KB |
Output is correct |
3 |
Correct |
459 ms |
303396 KB |
Output is correct |
4 |
Correct |
523 ms |
303380 KB |
Output is correct |
5 |
Correct |
449 ms |
303292 KB |
Output is correct |
6 |
Correct |
509 ms |
303388 KB |
Output is correct |
7 |
Correct |
533 ms |
303580 KB |
Output is correct |
8 |
Correct |
3 ms |
5076 KB |
Output is correct |
9 |
Correct |
170 ms |
238548 KB |
Output is correct |
10 |
Correct |
174 ms |
238532 KB |
Output is correct |
11 |
Correct |
159 ms |
238556 KB |
Output is correct |
12 |
Correct |
154 ms |
238524 KB |
Output is correct |
13 |
Correct |
168 ms |
238532 KB |
Output is correct |
14 |
Correct |
183 ms |
238584 KB |
Output is correct |
15 |
Correct |
168 ms |
238532 KB |
Output is correct |
16 |
Correct |
181 ms |
238508 KB |
Output is correct |
17 |
Correct |
155 ms |
238540 KB |
Output is correct |
18 |
Correct |
167 ms |
238500 KB |
Output is correct |
19 |
Correct |
249 ms |
238484 KB |
Output is correct |
20 |
Correct |
234 ms |
238612 KB |
Output is correct |
21 |
Correct |
3 ms |
5076 KB |
Output is correct |
22 |
Correct |
211 ms |
238536 KB |
Output is correct |
23 |
Correct |
230 ms |
238568 KB |
Output is correct |
24 |
Correct |
241 ms |
238584 KB |
Output is correct |
25 |
Correct |
275 ms |
238536 KB |
Output is correct |
26 |
Correct |
284 ms |
238604 KB |
Output is correct |
27 |
Correct |
256 ms |
238604 KB |
Output is correct |
28 |
Correct |
256 ms |
238664 KB |
Output is correct |
29 |
Correct |
199 ms |
238584 KB |
Output is correct |
30 |
Correct |
271 ms |
238576 KB |
Output is correct |
31 |
Correct |
319 ms |
238600 KB |
Output is correct |
32 |
Correct |
22 ms |
3028 KB |
Output is correct |
33 |
Correct |
50 ms |
3796 KB |
Output is correct |
34 |
Correct |
49 ms |
3796 KB |
Output is correct |
35 |
Correct |
328 ms |
3812 KB |
Output is correct |
36 |
Correct |
45 ms |
3796 KB |
Output is correct |
37 |
Execution timed out |
7015 ms |
3792 KB |
Time limit exceeded |
38 |
Halted |
0 ms |
0 KB |
- |