QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#95931#6308. MagicnodgdWA 2ms3752kbC++142.3kb2023-04-12 15:39:522023-04-12 15:39:54

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-12 15:39:54]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3752kb
  • [2023-04-12 15:39:52]
  • 提交

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'