#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, ll>
const ll oo = 1e18;
const int MAX = 400004, LOGMAX = 26;
const int logStart = 12;
int N;
vector<ll> S;
vector <int> st, P, W, L;
struct g{
array<ll, 3> par[LOGMAX][MAX];
void init(){
for (int j = 1; j < LOGMAX; j++)
{
for (int i = 0; i <= N; i++)
{
int m = par[j - 1][i][0];
par[j][i][0] = par[j - 1][m][0];
par[j][i][1] = par[j - 1][i][1] + par[j - 1][m][1];
par[j][i][2] = max(par[j - 1][i][2], par[j - 1][i][1] + par[j - 1][m][2]);
}
}
}
pii lift(int u, ll s, ll t){
if(u == N || s >= t){
return {u, s};
}
ll curs = s;
int v = u;
for (int j = LOGMAX - 1; j >= 0 && curs < t && v != N; j--)
{
if(curs + par[j][v][2] < 0){
curs += par[j][v][1];
v = par[j][v][0];
}
}
if(v == N) return {v, curs};
if(st[v] <= curs){
return make_pair(W[v], st[v] + curs);
}
else{
return make_pair(L[v], P[v] + curs);
}
}
};
g G[(LOGMAX - logStart) / 2];
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
N = n;
st = s;
P = p;
W = w;
L = l;
for (int i = logStart; i < LOGMAX; i += 2)
{
S.push_back(1ll << i);
}
for (int j = 0; j < S.size(); j++)
{
for (int i = 0; i < n; i++)
{
if(s[i] <= S[j]){
G[j].par[0][i] = {w[i], s[i], -oo};
}
else{
G[j].par[0][i] = {l[i], p[i], -s[i]};
}
}
}
for (int j = 0; j < S.size(); j++)
{
G[j].par[0][n] = {n, 0, -oo};
G[j].init();
}
S.push_back(oo);
}
ll simulate(int x, int z) {
ll X = x, Z = z;
while(Z < (1 << logStart) && X != N){
if(Z >= st[X]){
Z += st[X];
X = W[X];
}
else{
Z += P[X];
X = L[X];
}
}
for (int i = 0; i < S.size() - 1; i++)
{
while(Z < S[i + 1] && X != N){
pii a = G[i].lift(X, Z, S[i + 1]);
X = a.first, Z = a.second;
}
}
return Z;
}
Compilation message
dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int j = 0; j < S.size(); j++)
| ~~^~~~~~~~~~
dungeons.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int j = 0; j < S.size(); j++)
| ~~^~~~~~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for (int i = 0; i < S.size() - 1; i++)
| ~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1748 KB |
Output is correct |
2 |
Correct |
1 ms |
1748 KB |
Output is correct |
3 |
Correct |
5 ms |
10348 KB |
Output is correct |
4 |
Correct |
98 ms |
217732 KB |
Output is correct |
5 |
Correct |
6 ms |
10396 KB |
Output is correct |
6 |
Correct |
101 ms |
217716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
6100 KB |
Output is correct |
2 |
Correct |
927 ms |
1729488 KB |
Output is correct |
3 |
Correct |
1083 ms |
1729524 KB |
Output is correct |
4 |
Correct |
1040 ms |
1729524 KB |
Output is correct |
5 |
Correct |
893 ms |
1729612 KB |
Output is correct |
6 |
Correct |
1018 ms |
1729732 KB |
Output is correct |
7 |
Correct |
1050 ms |
1729612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
6084 KB |
Output is correct |
2 |
Correct |
241 ms |
218928 KB |
Output is correct |
3 |
Correct |
168 ms |
219060 KB |
Output is correct |
4 |
Correct |
131 ms |
218664 KB |
Output is correct |
5 |
Correct |
127 ms |
218716 KB |
Output is correct |
6 |
Correct |
194 ms |
218740 KB |
Output is correct |
7 |
Correct |
416 ms |
218880 KB |
Output is correct |
8 |
Correct |
153 ms |
218836 KB |
Output is correct |
9 |
Correct |
130 ms |
218900 KB |
Output is correct |
10 |
Correct |
221 ms |
218700 KB |
Output is correct |
11 |
Correct |
1647 ms |
218720 KB |
Output is correct |
12 |
Correct |
1935 ms |
218828 KB |
Output is correct |
13 |
Correct |
678 ms |
218740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
6084 KB |
Output is correct |
2 |
Correct |
241 ms |
218928 KB |
Output is correct |
3 |
Correct |
168 ms |
219060 KB |
Output is correct |
4 |
Correct |
131 ms |
218664 KB |
Output is correct |
5 |
Correct |
127 ms |
218716 KB |
Output is correct |
6 |
Correct |
194 ms |
218740 KB |
Output is correct |
7 |
Correct |
416 ms |
218880 KB |
Output is correct |
8 |
Correct |
153 ms |
218836 KB |
Output is correct |
9 |
Correct |
130 ms |
218900 KB |
Output is correct |
10 |
Correct |
221 ms |
218700 KB |
Output is correct |
11 |
Correct |
1647 ms |
218720 KB |
Output is correct |
12 |
Correct |
1935 ms |
218828 KB |
Output is correct |
13 |
Correct |
678 ms |
218740 KB |
Output is correct |
14 |
Correct |
4 ms |
6100 KB |
Output is correct |
15 |
Correct |
155 ms |
218924 KB |
Output is correct |
16 |
Correct |
180 ms |
218868 KB |
Output is correct |
17 |
Correct |
137 ms |
218696 KB |
Output is correct |
18 |
Correct |
154 ms |
218768 KB |
Output is correct |
19 |
Correct |
227 ms |
219068 KB |
Output is correct |
20 |
Correct |
181 ms |
218828 KB |
Output is correct |
21 |
Correct |
157 ms |
218728 KB |
Output is correct |
22 |
Correct |
717 ms |
218840 KB |
Output is correct |
23 |
Correct |
1908 ms |
218776 KB |
Output is correct |
24 |
Correct |
636 ms |
218832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
6084 KB |
Output is correct |
2 |
Correct |
241 ms |
218928 KB |
Output is correct |
3 |
Correct |
168 ms |
219060 KB |
Output is correct |
4 |
Correct |
131 ms |
218664 KB |
Output is correct |
5 |
Correct |
127 ms |
218716 KB |
Output is correct |
6 |
Correct |
194 ms |
218740 KB |
Output is correct |
7 |
Correct |
416 ms |
218880 KB |
Output is correct |
8 |
Correct |
153 ms |
218836 KB |
Output is correct |
9 |
Correct |
130 ms |
218900 KB |
Output is correct |
10 |
Correct |
221 ms |
218700 KB |
Output is correct |
11 |
Correct |
1647 ms |
218720 KB |
Output is correct |
12 |
Correct |
1935 ms |
218828 KB |
Output is correct |
13 |
Correct |
678 ms |
218740 KB |
Output is correct |
14 |
Correct |
4 ms |
6100 KB |
Output is correct |
15 |
Correct |
155 ms |
218924 KB |
Output is correct |
16 |
Correct |
180 ms |
218868 KB |
Output is correct |
17 |
Correct |
137 ms |
218696 KB |
Output is correct |
18 |
Correct |
154 ms |
218768 KB |
Output is correct |
19 |
Correct |
227 ms |
219068 KB |
Output is correct |
20 |
Correct |
181 ms |
218828 KB |
Output is correct |
21 |
Correct |
157 ms |
218728 KB |
Output is correct |
22 |
Correct |
717 ms |
218840 KB |
Output is correct |
23 |
Correct |
1908 ms |
218776 KB |
Output is correct |
24 |
Correct |
636 ms |
218832 KB |
Output is correct |
25 |
Correct |
123 ms |
218168 KB |
Output is correct |
26 |
Correct |
186 ms |
219072 KB |
Output is correct |
27 |
Correct |
153 ms |
218700 KB |
Output is correct |
28 |
Correct |
177 ms |
218580 KB |
Output is correct |
29 |
Correct |
197 ms |
219040 KB |
Output is correct |
30 |
Correct |
218 ms |
218804 KB |
Output is correct |
31 |
Correct |
215 ms |
218892 KB |
Output is correct |
32 |
Correct |
512 ms |
218896 KB |
Output is correct |
33 |
Correct |
526 ms |
218828 KB |
Output is correct |
34 |
Correct |
1157 ms |
218700 KB |
Output is correct |
35 |
Correct |
460 ms |
218844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
6100 KB |
Output is correct |
2 |
Correct |
927 ms |
1729488 KB |
Output is correct |
3 |
Correct |
1083 ms |
1729524 KB |
Output is correct |
4 |
Correct |
1040 ms |
1729524 KB |
Output is correct |
5 |
Correct |
893 ms |
1729612 KB |
Output is correct |
6 |
Correct |
1018 ms |
1729732 KB |
Output is correct |
7 |
Correct |
1050 ms |
1729612 KB |
Output is correct |
8 |
Correct |
4 ms |
6084 KB |
Output is correct |
9 |
Correct |
241 ms |
218928 KB |
Output is correct |
10 |
Correct |
168 ms |
219060 KB |
Output is correct |
11 |
Correct |
131 ms |
218664 KB |
Output is correct |
12 |
Correct |
127 ms |
218716 KB |
Output is correct |
13 |
Correct |
194 ms |
218740 KB |
Output is correct |
14 |
Correct |
416 ms |
218880 KB |
Output is correct |
15 |
Correct |
153 ms |
218836 KB |
Output is correct |
16 |
Correct |
130 ms |
218900 KB |
Output is correct |
17 |
Correct |
221 ms |
218700 KB |
Output is correct |
18 |
Correct |
1647 ms |
218720 KB |
Output is correct |
19 |
Correct |
1935 ms |
218828 KB |
Output is correct |
20 |
Correct |
678 ms |
218740 KB |
Output is correct |
21 |
Correct |
4 ms |
6100 KB |
Output is correct |
22 |
Correct |
155 ms |
218924 KB |
Output is correct |
23 |
Correct |
180 ms |
218868 KB |
Output is correct |
24 |
Correct |
137 ms |
218696 KB |
Output is correct |
25 |
Correct |
154 ms |
218768 KB |
Output is correct |
26 |
Correct |
227 ms |
219068 KB |
Output is correct |
27 |
Correct |
181 ms |
218828 KB |
Output is correct |
28 |
Correct |
157 ms |
218728 KB |
Output is correct |
29 |
Correct |
717 ms |
218840 KB |
Output is correct |
30 |
Correct |
1908 ms |
218776 KB |
Output is correct |
31 |
Correct |
636 ms |
218832 KB |
Output is correct |
32 |
Correct |
123 ms |
218168 KB |
Output is correct |
33 |
Correct |
186 ms |
219072 KB |
Output is correct |
34 |
Correct |
153 ms |
218700 KB |
Output is correct |
35 |
Correct |
177 ms |
218580 KB |
Output is correct |
36 |
Correct |
197 ms |
219040 KB |
Output is correct |
37 |
Correct |
218 ms |
218804 KB |
Output is correct |
38 |
Correct |
215 ms |
218892 KB |
Output is correct |
39 |
Correct |
512 ms |
218896 KB |
Output is correct |
40 |
Correct |
526 ms |
218828 KB |
Output is correct |
41 |
Correct |
1157 ms |
218700 KB |
Output is correct |
42 |
Correct |
460 ms |
218844 KB |
Output is correct |
43 |
Correct |
1 ms |
1748 KB |
Output is correct |
44 |
Correct |
4 ms |
6136 KB |
Output is correct |
45 |
Correct |
1097 ms |
1733980 KB |
Output is correct |
46 |
Correct |
857 ms |
1730660 KB |
Output is correct |
47 |
Correct |
872 ms |
1734164 KB |
Output is correct |
48 |
Correct |
889 ms |
1739012 KB |
Output is correct |
49 |
Correct |
1118 ms |
1741000 KB |
Output is correct |
50 |
Correct |
923 ms |
1738632 KB |
Output is correct |
51 |
Correct |
866 ms |
1738960 KB |
Output is correct |
52 |
Correct |
963 ms |
1736728 KB |
Output is correct |
53 |
Correct |
1963 ms |
1737440 KB |
Output is correct |
54 |
Correct |
1726 ms |
1738720 KB |
Output is correct |
55 |
Correct |
2446 ms |
1737540 KB |
Output is correct |
56 |
Correct |
1814 ms |
1738192 KB |
Output is correct |
57 |
Correct |
1794 ms |
1738312 KB |
Output is correct |
58 |
Correct |
1982 ms |
1738380 KB |
Output is correct |
59 |
Correct |
1793 ms |
1738564 KB |
Output is correct |
60 |
Correct |
1970 ms |
1737788 KB |
Output is correct |
61 |
Correct |
1825 ms |
1737784 KB |
Output is correct |