QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#95931 | #6308. Magic | nodgd | WA | 2ms | 3752kb | C++14 | 2.3kb | 2023-04-12 15:39:52 | 2023-04-12 15:39:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int MAX_N = 5000 + 5;
const i64 INF64 = 1e18;
int N, S;
int aw[MAX_N], ap[MAX_N], go[MAX_N];
int R, rv[MAX_N], rk[MAX_N], H, h[MAX_N];
i64 ans, f[MAX_N][MAX_N], g[MAX_N][3];
vector<int> son[MAX_N];
void dfs(int u) {
for (int v: son[u]) dfs(v), h[u] = max(h[u], h[v] + 1);
}
void init_ring_tree() {
for (int i = 1, x = S; i <= N << 1; i ++, x = go[x]) rk[x] ++;
for (int i = 1; i <= N; i ++) R += rk[i] = rk[i] >= 2;
for (int i = 1; i <= N; i ++) if (!rk[i]) son[go[i]].push_back(i);
if (!rk[S]) return;
for (int i = R, x = S; i >= 1; i --) rv[i] = x = go[x];
for (int i = 1; i <= R; i ++) dfs(rv[i]), H = max(H, h[rv[i]] + 2);
}
void dp(int u) {
for (int v: son[u]) dp(v);
for (int v: son[u]) {
for (i64 k = 0, t = -INF64; k <= H; k ++) {
f[u][k] += t = max(t, f[v][k]);
}
}
for (int k = 0; k <= H; k ++) {
f[u][k] += (k & 1) * aw[u];
f[u][k] -= 1ll * (k - (u == S)) * ap[u];
}
if (u == S) f[u][0] = -INF64;
}
int main() {
scanf("%d%d", &N, &S);
for (int i = 1; i <= N; i ++) scanf("%d", &aw[i]);
for (int i = 1; i <= N; i ++) scanf("%d", &ap[i]);
for (int i = 1; i <= N; i ++) scanf("%d", &go[i]);
init_ring_tree();
if (aw[1] == 830648318) printf("rk[S]=%d,R=%d,", rk[S], R);
if (!rk[S]) {
dfs(S), H = max(H, h[S] + 1);
dp(S), ans = max(f[S][1], f[S][2]);
} else if (R == 2) {
dp(S), dp(rv[2]);
ans = max(f[S][2], f[S][1] + max(f[rv[2]][0], f[rv[2]][1]));
} else {
H = max(H, 3), ans = -INF64;
for (int i = 1; i <= R; i ++) dp(rv[i]);
for (int k = 1; k <= H; k ++) {
g[1][0] = f[S][k], g[1][1] = g[1][2] = -INF64;
for (int i = 2; i <= R; i ++) {
if (k >= 2) g[i][2] = max(max(g[i - 1][0], g[i - 1][1]), g[i - 1][2]) + f[rv[i]][k - 2];
g[i][1] = max(g[i - 1][0], g[i - 1][1]) + f[rv[i]][k - 1];
g[i][0] = g[i - 1][0] + f[rv[i]][k];
}
if (k >= 2) ans = max(ans, g[R][2]);
ans = max(ans, max(g[R][1], g[R][0]));
}
}
printf("%lld\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3752kb
input:
5 2 3 6 7 1 9 5 10 4 8
output:
6
result:
wrong answer 1st numbers differ - expected: '9', found: '6'