#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=4e5+5, lx=8, kx=25;
ll N, pw[20], dist[nx];
vector<int> S(nx), P(nx), W(nx), L(nx);
struct edge
{
int out;
ll cost, t;
edge(int out=0, ll cost=0, ll t=0): out(out), cost(cost), t(t){}
} dp[lx][nx][kx];
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
N=n;
pw[0]=1;
for (int i=1; i<20; i++) pw[i]=pw[i-1]*8;
for (int i=0; i<n; i++) S[i]=s[i], P[i]=p[i], W[i]=w[i], L[i]=l[i];
for (int i=n-1; i>=0; i--) dist[i]=dist[w[i]]+s[i];
W[n]=L[n]=n;
for (int i=0; i<lx; i++)
{
for (int u=0; u<=n; u++)
{
if (s[u]<=pw[i]) dp[i][u][0]=edge(W[u], S[u], 1e18);
else dp[i][u][0]=edge(L[u], P[u], S[u]);
}
for (int j=1; j<kx; j++)
{
for (int u=0; u<=n; u++)
{
int v=dp[i][u][j-1].out;
ll out=dp[i][v][j-1].out;
ll cost=dp[i][u][j-1].cost+dp[i][v][j-1].cost;
ll t=min(dp[i][u][j-1].t, dp[i][v][j-1].t-dp[i][u][j-1].cost);
dp[i][u][j]=edge(out, cost, t);
}
}
}
}
long long simulate(int x, int z) {
ll cur=z, st=0;
while (x!=N&&cur<1e7)
{
//cout<<"debug "<<x<<' '<<cur<<' '<<st<<'\n';
while (st+1<lx&&pw[st+1]<=cur) st++;
for (int i=kx-1; i>=0; i--) if (dp[st][x][i].t>cur) cur+=dp[st][x][i].cost, x=dp[st][x][i].out; //cout<<"here "<<i<<' '<<cur<<' '<<x<<'\n';
//cout<<"after "<<x<<' '<<cur<<' '<<st<<'\n';
if (cur>=S[x]) cur+=S[x], x=W[x];
else cur+=P[x], x=L[x];
}
return cur+dist[x];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
925 ms |
1886376 KB |
Output is correct |
2 |
Correct |
650 ms |
1886320 KB |
Output is correct |
3 |
Correct |
623 ms |
1886612 KB |
Output is correct |
4 |
Correct |
740 ms |
1889120 KB |
Output is correct |
5 |
Correct |
677 ms |
1886404 KB |
Output is correct |
6 |
Correct |
735 ms |
1889104 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
766 ms |
1886548 KB |
Output is correct |
2 |
Correct |
2430 ms |
1902324 KB |
Output is correct |
3 |
Correct |
2177 ms |
1908724 KB |
Output is correct |
4 |
Correct |
2138 ms |
1910256 KB |
Output is correct |
5 |
Correct |
2087 ms |
1908232 KB |
Output is correct |
6 |
Correct |
2380 ms |
1904436 KB |
Output is correct |
7 |
Correct |
2222 ms |
1903696 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
657 ms |
1886324 KB |
Output is correct |
2 |
Correct |
723 ms |
1889552 KB |
Output is correct |
3 |
Correct |
712 ms |
1889596 KB |
Output is correct |
4 |
Correct |
708 ms |
1889928 KB |
Output is correct |
5 |
Correct |
710 ms |
1889912 KB |
Output is correct |
6 |
Correct |
746 ms |
1890108 KB |
Output is correct |
7 |
Correct |
752 ms |
1890132 KB |
Output is correct |
8 |
Correct |
695 ms |
1889872 KB |
Output is correct |
9 |
Correct |
710 ms |
1889828 KB |
Output is correct |
10 |
Correct |
704 ms |
1889496 KB |
Output is correct |
11 |
Correct |
740 ms |
1890148 KB |
Output is correct |
12 |
Correct |
818 ms |
1890020 KB |
Output is correct |
13 |
Correct |
809 ms |
1890252 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
657 ms |
1886324 KB |
Output is correct |
2 |
Correct |
723 ms |
1889552 KB |
Output is correct |
3 |
Correct |
712 ms |
1889596 KB |
Output is correct |
4 |
Correct |
708 ms |
1889928 KB |
Output is correct |
5 |
Correct |
710 ms |
1889912 KB |
Output is correct |
6 |
Correct |
746 ms |
1890108 KB |
Output is correct |
7 |
Correct |
752 ms |
1890132 KB |
Output is correct |
8 |
Correct |
695 ms |
1889872 KB |
Output is correct |
9 |
Correct |
710 ms |
1889828 KB |
Output is correct |
10 |
Correct |
704 ms |
1889496 KB |
Output is correct |
11 |
Correct |
740 ms |
1890148 KB |
Output is correct |
12 |
Correct |
818 ms |
1890020 KB |
Output is correct |
13 |
Correct |
809 ms |
1890252 KB |
Output is correct |
14 |
Correct |
606 ms |
1886632 KB |
Output is correct |
15 |
Correct |
859 ms |
1890368 KB |
Output is correct |
16 |
Correct |
909 ms |
1890596 KB |
Output is correct |
17 |
Correct |
731 ms |
1889868 KB |
Output is correct |
18 |
Correct |
761 ms |
1890184 KB |
Output is correct |
19 |
Correct |
719 ms |
1889988 KB |
Output is correct |
20 |
Correct |
711 ms |
1889856 KB |
Output is correct |
21 |
Correct |
731 ms |
1889884 KB |
Output is correct |
22 |
Correct |
719 ms |
1889996 KB |
Output is correct |
23 |
Correct |
721 ms |
1890008 KB |
Output is correct |
24 |
Correct |
870 ms |
1890084 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
657 ms |
1886324 KB |
Output is correct |
2 |
Correct |
723 ms |
1889552 KB |
Output is correct |
3 |
Correct |
712 ms |
1889596 KB |
Output is correct |
4 |
Correct |
708 ms |
1889928 KB |
Output is correct |
5 |
Correct |
710 ms |
1889912 KB |
Output is correct |
6 |
Correct |
746 ms |
1890108 KB |
Output is correct |
7 |
Correct |
752 ms |
1890132 KB |
Output is correct |
8 |
Correct |
695 ms |
1889872 KB |
Output is correct |
9 |
Correct |
710 ms |
1889828 KB |
Output is correct |
10 |
Correct |
704 ms |
1889496 KB |
Output is correct |
11 |
Correct |
740 ms |
1890148 KB |
Output is correct |
12 |
Correct |
818 ms |
1890020 KB |
Output is correct |
13 |
Correct |
809 ms |
1890252 KB |
Output is correct |
14 |
Correct |
606 ms |
1886632 KB |
Output is correct |
15 |
Correct |
859 ms |
1890368 KB |
Output is correct |
16 |
Correct |
909 ms |
1890596 KB |
Output is correct |
17 |
Correct |
731 ms |
1889868 KB |
Output is correct |
18 |
Correct |
761 ms |
1890184 KB |
Output is correct |
19 |
Correct |
719 ms |
1889988 KB |
Output is correct |
20 |
Correct |
711 ms |
1889856 KB |
Output is correct |
21 |
Correct |
731 ms |
1889884 KB |
Output is correct |
22 |
Correct |
719 ms |
1889996 KB |
Output is correct |
23 |
Correct |
721 ms |
1890008 KB |
Output is correct |
24 |
Correct |
870 ms |
1890084 KB |
Output is correct |
25 |
Correct |
701 ms |
1889560 KB |
Output is correct |
26 |
Correct |
746 ms |
1890376 KB |
Output is correct |
27 |
Correct |
723 ms |
1889880 KB |
Output is correct |
28 |
Correct |
694 ms |
1890212 KB |
Output is correct |
29 |
Correct |
735 ms |
1890452 KB |
Output is correct |
30 |
Correct |
740 ms |
1890164 KB |
Output is correct |
31 |
Correct |
749 ms |
1890052 KB |
Output is correct |
32 |
Correct |
815 ms |
1889872 KB |
Output is correct |
33 |
Correct |
887 ms |
1890120 KB |
Output is correct |
34 |
Correct |
1283 ms |
1889988 KB |
Output is correct |
35 |
Correct |
803 ms |
1889780 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
766 ms |
1886548 KB |
Output is correct |
2 |
Correct |
2430 ms |
1902324 KB |
Output is correct |
3 |
Correct |
2177 ms |
1908724 KB |
Output is correct |
4 |
Correct |
2138 ms |
1910256 KB |
Output is correct |
5 |
Correct |
2087 ms |
1908232 KB |
Output is correct |
6 |
Correct |
2380 ms |
1904436 KB |
Output is correct |
7 |
Correct |
2222 ms |
1903696 KB |
Output is correct |
8 |
Correct |
657 ms |
1886324 KB |
Output is correct |
9 |
Correct |
723 ms |
1889552 KB |
Output is correct |
10 |
Correct |
712 ms |
1889596 KB |
Output is correct |
11 |
Correct |
708 ms |
1889928 KB |
Output is correct |
12 |
Correct |
710 ms |
1889912 KB |
Output is correct |
13 |
Correct |
746 ms |
1890108 KB |
Output is correct |
14 |
Correct |
752 ms |
1890132 KB |
Output is correct |
15 |
Correct |
695 ms |
1889872 KB |
Output is correct |
16 |
Correct |
710 ms |
1889828 KB |
Output is correct |
17 |
Correct |
704 ms |
1889496 KB |
Output is correct |
18 |
Correct |
740 ms |
1890148 KB |
Output is correct |
19 |
Correct |
818 ms |
1890020 KB |
Output is correct |
20 |
Correct |
809 ms |
1890252 KB |
Output is correct |
21 |
Correct |
606 ms |
1886632 KB |
Output is correct |
22 |
Correct |
859 ms |
1890368 KB |
Output is correct |
23 |
Correct |
909 ms |
1890596 KB |
Output is correct |
24 |
Correct |
731 ms |
1889868 KB |
Output is correct |
25 |
Correct |
761 ms |
1890184 KB |
Output is correct |
26 |
Correct |
719 ms |
1889988 KB |
Output is correct |
27 |
Correct |
711 ms |
1889856 KB |
Output is correct |
28 |
Correct |
731 ms |
1889884 KB |
Output is correct |
29 |
Correct |
719 ms |
1889996 KB |
Output is correct |
30 |
Correct |
721 ms |
1890008 KB |
Output is correct |
31 |
Correct |
870 ms |
1890084 KB |
Output is correct |
32 |
Correct |
701 ms |
1889560 KB |
Output is correct |
33 |
Correct |
746 ms |
1890376 KB |
Output is correct |
34 |
Correct |
723 ms |
1889880 KB |
Output is correct |
35 |
Correct |
694 ms |
1890212 KB |
Output is correct |
36 |
Correct |
735 ms |
1890452 KB |
Output is correct |
37 |
Correct |
740 ms |
1890164 KB |
Output is correct |
38 |
Correct |
749 ms |
1890052 KB |
Output is correct |
39 |
Correct |
815 ms |
1889872 KB |
Output is correct |
40 |
Correct |
887 ms |
1890120 KB |
Output is correct |
41 |
Correct |
1283 ms |
1889988 KB |
Output is correct |
42 |
Correct |
803 ms |
1889780 KB |
Output is correct |
43 |
Correct |
592 ms |
1886288 KB |
Output is correct |
44 |
Correct |
598 ms |
1886512 KB |
Output is correct |
45 |
Correct |
2217 ms |
1913484 KB |
Output is correct |
46 |
Correct |
2091 ms |
1908880 KB |
Output is correct |
47 |
Correct |
2085 ms |
1909260 KB |
Output is correct |
48 |
Correct |
2043 ms |
1911440 KB |
Output is correct |
49 |
Correct |
2239 ms |
1913652 KB |
Output is correct |
50 |
Correct |
2412 ms |
1911056 KB |
Output is correct |
51 |
Correct |
2072 ms |
1911480 KB |
Output is correct |
52 |
Correct |
2342 ms |
1909284 KB |
Output is correct |
53 |
Correct |
2832 ms |
1909900 KB |
Output is correct |
54 |
Correct |
2794 ms |
1911108 KB |
Output is correct |
55 |
Correct |
3624 ms |
1910304 KB |
Output is correct |
56 |
Correct |
2582 ms |
1910672 KB |
Output is correct |
57 |
Correct |
2985 ms |
1910752 KB |
Output is correct |
58 |
Correct |
2766 ms |
1910800 KB |
Output is correct |
59 |
Correct |
2696 ms |
1910924 KB |
Output is correct |
60 |
Correct |
3288 ms |
1910160 KB |
Output is correct |
61 |
Correct |
3245 ms |
1910160 KB |
Output is correct |