#include "dungeons.h"
#include<bits/stdc++.h>
#define pii pair<long long, long long>
#define f first
#define s second
using namespace std;
#include <vector>
vector<int> s, p, w, l;
int n;
const long long inf = 1e18;
const int N =4e5 + 5;
long long nxt[N][33][6], add[N][33][6], d[N][2], F, mx[N][33];
vector<int> val;
vector<pii> V[N][2];
void bfs(int t) {
for(int i = 0; i < n; i++) d[i][t] = inf;
queue<int> q;
q.push(n);
while(q.size()) {
int u = q.front();
q.pop();
for(int i = 0; i < V[u][t].size(); i++) {
d[V[u][t][i].f][t] = d[u][t] + V[u][t][i].s;
q.push(V[u][t][i].f);
}
}
}
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
s = S; p = P; w = W; l = L;
n = N;
F = 1;
for(int i = 0; i < n; i++) F &= (s[i] == p[i]);
for(int i = 0; i < n; i++) {
val.push_back(s[i]);
}
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
if(val.size() <= 5 && n <= 50000) {
for(int i = 0; i < n; i++) nxt[i][0][0] = l[i], add[i][0][0] = p[i];
nxt[n][0][0] = nxt[n][0][1] = n;
mx[n][0] = -inf;
for(int i = 0; i < val.size(); i++) {
nxt[n][0][i + 1] = n;
for(int j = 0; j < n; j++) {
if(s[j] <= val[i]) {
nxt[j][0][i + 1] = w[j];
add[j][0][i + 1] = s[j];
} else nxt[j][0][i + 1] = l[j], add[j][0][i + 1] = p[j];
}
}
for(int i = 1; i <= 30; i++) {
for(int j = 0; j <= n; j++) {
for(int t = 0; t <= val.size(); t++)
nxt[j][i][t] = nxt[nxt[j][i - 1][t]][i - 1][t],
add[j][i][t] = add[j][i - 1][t] + add[nxt[j][i - 1][t]][i - 1][t];
int t = 1;
mx[j][i] = max(mx[j][i - 1], -add[j][i - 1][t] + mx[nxt[j][i - 1][t]][i - 1]);
}
}
for(int i = 0; i < n; i++) {
V[w[i]][0].push_back({i, s[i]});
}
bfs(0);}
else {
mx[n][0] = -1e9;
for(int i = 0; i < n; i++) nxt[i][0][1] = w[i], add[i][0][1] = s[i], mx[i][0] = s[i];
nxt[n][0][0] = nxt[n][0][1] = n;
for(int i = 1; i <= 30; i++) {
for(int j = 0; j <= n; j++) {
for(int t = 0; t < 2; t++)
nxt[j][i][t] = nxt[nxt[j][i - 1][t]][i - 1][t],
add[j][i][t] = add[j][i - 1][t] + add[nxt[j][i - 1][t]][i - 1][t];
int t = 1;
mx[j][i] = max(mx[j][i - 1], -add[j][i - 1][t] + mx[nxt[j][i - 1][t]][i - 1]);
}
}
}
}
long long get2(int x, int Z) {
long long ans2 = Z;
while(x != n) {
// cout << x << endl; system("pause");
for(int i = 30; i >= 0; i--) {
if(mx[x][i] <= ans2) {
ans2 += add[x][i][1];
x = nxt[x][i][1];
} //else cout << "+" << 30 << endl;
}
if(x == n) break;
ans2 += s[x];
x = l[x];
}
return ans2;
}
long long get3(int x,int Z) {
long long ans2 = Z;
for(int k = 0; k < val.size(); k++) {
for(int i = 30; i >= 0; i--) {
if(add[x][i][k] + ans2 < val[k]) {
ans2 += add[x][i][k];
x = nxt[x][i][k];
}
}
if(ans2 < val[k]) {
ans2 += add[x][0][k];
x = nxt[x][0][k];
}
}
return ans2 + d[x][0];
}
long long simulate(int x, int Z) {
if(val.size() <= 5 && n <= 50000) return get3(x, Z);
if(F) return get2(x, Z);
long long z = Z;
while(x != n) {
if(z < s[x]) {
z += p[x];
x = l[x];
} else z += s[x], x = w[x];
}
return z;
}
Compilation message
dungeons.cpp: In function 'void bfs(int)':
dungeons.cpp:22:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i = 0; i < V[u][t].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i = 0; i < val.size(); i++) {
| ~~^~~~~~~~~~~~
dungeons.cpp:53:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int t = 0; t <= val.size(); t++)
| ~~^~~~~~~~~~~~~
dungeons.cpp: In function 'long long int get3(int, int)':
dungeons.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int k = 0; k < val.size(); k++) {
| ~~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
19028 KB |
Output is correct |
2 |
Correct |
11 ms |
19156 KB |
Output is correct |
3 |
Correct |
17 ms |
25940 KB |
Output is correct |
4 |
Correct |
150 ms |
189736 KB |
Output is correct |
5 |
Correct |
14 ms |
25956 KB |
Output is correct |
6 |
Correct |
139 ms |
189616 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
22508 KB |
Output is correct |
2 |
Correct |
1287 ms |
1383552 KB |
Output is correct |
3 |
Correct |
1131 ms |
1390648 KB |
Output is correct |
4 |
Correct |
1114 ms |
1392072 KB |
Output is correct |
5 |
Correct |
1171 ms |
1392060 KB |
Output is correct |
6 |
Correct |
1167 ms |
1390580 KB |
Output is correct |
7 |
Correct |
1130 ms |
1388860 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
22612 KB |
Output is correct |
2 |
Correct |
213 ms |
192840 KB |
Output is correct |
3 |
Correct |
201 ms |
192768 KB |
Output is correct |
4 |
Correct |
188 ms |
192912 KB |
Output is correct |
5 |
Correct |
197 ms |
192696 KB |
Output is correct |
6 |
Correct |
197 ms |
192720 KB |
Output is correct |
7 |
Correct |
217 ms |
192736 KB |
Output is correct |
8 |
Correct |
215 ms |
193028 KB |
Output is correct |
9 |
Correct |
201 ms |
192592 KB |
Output is correct |
10 |
Correct |
192 ms |
192912 KB |
Output is correct |
11 |
Correct |
210 ms |
192904 KB |
Output is correct |
12 |
Correct |
306 ms |
192684 KB |
Output is correct |
13 |
Correct |
280 ms |
192216 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
22612 KB |
Output is correct |
2 |
Correct |
213 ms |
192840 KB |
Output is correct |
3 |
Correct |
201 ms |
192768 KB |
Output is correct |
4 |
Correct |
188 ms |
192912 KB |
Output is correct |
5 |
Correct |
197 ms |
192696 KB |
Output is correct |
6 |
Correct |
197 ms |
192720 KB |
Output is correct |
7 |
Correct |
217 ms |
192736 KB |
Output is correct |
8 |
Correct |
215 ms |
193028 KB |
Output is correct |
9 |
Correct |
201 ms |
192592 KB |
Output is correct |
10 |
Correct |
192 ms |
192912 KB |
Output is correct |
11 |
Correct |
210 ms |
192904 KB |
Output is correct |
12 |
Correct |
306 ms |
192684 KB |
Output is correct |
13 |
Correct |
280 ms |
192216 KB |
Output is correct |
14 |
Correct |
13 ms |
22484 KB |
Output is correct |
15 |
Correct |
291 ms |
192436 KB |
Output is correct |
16 |
Correct |
333 ms |
192444 KB |
Output is correct |
17 |
Correct |
325 ms |
192456 KB |
Output is correct |
18 |
Correct |
388 ms |
192476 KB |
Output is correct |
19 |
Correct |
387 ms |
192660 KB |
Output is correct |
20 |
Correct |
315 ms |
192416 KB |
Output is correct |
21 |
Correct |
340 ms |
192520 KB |
Output is correct |
22 |
Correct |
280 ms |
192400 KB |
Output is correct |
23 |
Correct |
351 ms |
192600 KB |
Output is correct |
24 |
Correct |
441 ms |
192492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
22612 KB |
Output is correct |
2 |
Correct |
213 ms |
192840 KB |
Output is correct |
3 |
Correct |
201 ms |
192768 KB |
Output is correct |
4 |
Correct |
188 ms |
192912 KB |
Output is correct |
5 |
Correct |
197 ms |
192696 KB |
Output is correct |
6 |
Correct |
197 ms |
192720 KB |
Output is correct |
7 |
Correct |
217 ms |
192736 KB |
Output is correct |
8 |
Correct |
215 ms |
193028 KB |
Output is correct |
9 |
Correct |
201 ms |
192592 KB |
Output is correct |
10 |
Correct |
192 ms |
192912 KB |
Output is correct |
11 |
Correct |
210 ms |
192904 KB |
Output is correct |
12 |
Correct |
306 ms |
192684 KB |
Output is correct |
13 |
Correct |
280 ms |
192216 KB |
Output is correct |
14 |
Correct |
13 ms |
22484 KB |
Output is correct |
15 |
Correct |
291 ms |
192436 KB |
Output is correct |
16 |
Correct |
333 ms |
192444 KB |
Output is correct |
17 |
Correct |
325 ms |
192456 KB |
Output is correct |
18 |
Correct |
388 ms |
192476 KB |
Output is correct |
19 |
Correct |
387 ms |
192660 KB |
Output is correct |
20 |
Correct |
315 ms |
192416 KB |
Output is correct |
21 |
Correct |
340 ms |
192520 KB |
Output is correct |
22 |
Correct |
280 ms |
192400 KB |
Output is correct |
23 |
Correct |
351 ms |
192600 KB |
Output is correct |
24 |
Correct |
441 ms |
192492 KB |
Output is correct |
25 |
Correct |
153 ms |
189668 KB |
Output is correct |
26 |
Correct |
169 ms |
190664 KB |
Output is correct |
27 |
Correct |
168 ms |
190664 KB |
Output is correct |
28 |
Correct |
443 ms |
190760 KB |
Output is correct |
29 |
Correct |
179 ms |
190660 KB |
Output is correct |
30 |
Execution timed out |
7045 ms |
190904 KB |
Time limit exceeded |
31 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
22508 KB |
Output is correct |
2 |
Correct |
1287 ms |
1383552 KB |
Output is correct |
3 |
Correct |
1131 ms |
1390648 KB |
Output is correct |
4 |
Correct |
1114 ms |
1392072 KB |
Output is correct |
5 |
Correct |
1171 ms |
1392060 KB |
Output is correct |
6 |
Correct |
1167 ms |
1390580 KB |
Output is correct |
7 |
Correct |
1130 ms |
1388860 KB |
Output is correct |
8 |
Correct |
13 ms |
22612 KB |
Output is correct |
9 |
Correct |
213 ms |
192840 KB |
Output is correct |
10 |
Correct |
201 ms |
192768 KB |
Output is correct |
11 |
Correct |
188 ms |
192912 KB |
Output is correct |
12 |
Correct |
197 ms |
192696 KB |
Output is correct |
13 |
Correct |
197 ms |
192720 KB |
Output is correct |
14 |
Correct |
217 ms |
192736 KB |
Output is correct |
15 |
Correct |
215 ms |
193028 KB |
Output is correct |
16 |
Correct |
201 ms |
192592 KB |
Output is correct |
17 |
Correct |
192 ms |
192912 KB |
Output is correct |
18 |
Correct |
210 ms |
192904 KB |
Output is correct |
19 |
Correct |
306 ms |
192684 KB |
Output is correct |
20 |
Correct |
280 ms |
192216 KB |
Output is correct |
21 |
Correct |
13 ms |
22484 KB |
Output is correct |
22 |
Correct |
291 ms |
192436 KB |
Output is correct |
23 |
Correct |
333 ms |
192444 KB |
Output is correct |
24 |
Correct |
325 ms |
192456 KB |
Output is correct |
25 |
Correct |
388 ms |
192476 KB |
Output is correct |
26 |
Correct |
387 ms |
192660 KB |
Output is correct |
27 |
Correct |
315 ms |
192416 KB |
Output is correct |
28 |
Correct |
340 ms |
192520 KB |
Output is correct |
29 |
Correct |
280 ms |
192400 KB |
Output is correct |
30 |
Correct |
351 ms |
192600 KB |
Output is correct |
31 |
Correct |
441 ms |
192492 KB |
Output is correct |
32 |
Correct |
153 ms |
189668 KB |
Output is correct |
33 |
Correct |
169 ms |
190664 KB |
Output is correct |
34 |
Correct |
168 ms |
190664 KB |
Output is correct |
35 |
Correct |
443 ms |
190760 KB |
Output is correct |
36 |
Correct |
179 ms |
190660 KB |
Output is correct |
37 |
Execution timed out |
7045 ms |
190904 KB |
Time limit exceeded |
38 |
Halted |
0 ms |
0 KB |
- |