oj.uz

Submission #765806

# Submission time Handle Problem Language Result Execution time Memory
765806 2023-06-25T05:33:18 Z fefe Wombats (IOI13_wombats) C++17
55 / 100
 418 ms 262144 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;

const int inf = 0x3fffffff;

// duplication of the original data
int r, c;
int h[5000][200], v[5000][200];

// related with 3-way segment tree
int n;
int DP[8281][200][200];
int LC[8281], MC[8281], RC[8281];



// array used in merge function
int D[200][200];
int temp[200][200];
void merge(int A[200][200], int B[200][200], int cost[200], int M[200][200]) {
    // s == e
    for (int i = 0; i < c; i++) {
        temp[i][i] = inf;
        D[i][i] = i;
        for (int j = 0; j < c; j++) {
            if (temp[i][i] > A[i][j] + cost[j] + B[j][i]) {
                temp[i][i] = A[i][j] + cost[j] + B[j][i];
                D[i][i] = j;
            }
        }
    }

    // s < e

    for (int len = 2; len <= c; len++) {
        for (int s = 0; s <= c - len; s++) {
            int e = s + len - 1;
            temp[s][e] = inf;
            D[s][e] = s;
            for (int i = D[s][e - 1]; i <= D[s + 1][e]; i++) {
                if (temp[s][e] > A[s][i] + cost[i] + B[i][e]) {
                    temp[s][e] = A[s][i] + cost[i] + B[i][e];
                    D[s][e] = i;
                }
            }

        }
    }

    // s > e

    for (int len = 2; len <= c; len++) {
        for (int s = len - 1; s < c; s++) {
            int e = s - len + 1;
            temp[s][e] = inf;
            D[s][e] = s;
            for (int i = D[s - 1][e]; i <= D[s][e + 1]; i++) {
                if (temp[s][e] > A[s][i] + cost[i] + B[i][e]) {
                    temp[s][e] = A[s][i] + cost[i] + B[i][e];
                    D[s][e] = i;
                }
            }
        }
    }

    for (int s = 0; s < c; s++) {
        for (int e = 0; e < c; e++) {
            M[s][e] = temp[s][e];
        }
    }
}

void set_mono_dp(int u, int i) {
    for (int s = 0; s < c; s++) {
        DP[u][s][s] = 0;
        for (int e = s + 1; e < c; e++) {
            DP[u][s][e] = DP[u][s][e - 1] + h[i][e - 1];
            DP[u][e][s] = DP[u][s][e];
        }
    }
}

void init_seg(int u, int l, int r) {
    if (l == r) {
        set_mono_dp(u, l);
    }

    else if (l + 1 == r) {
        LC[u] = ++n;
        RC[u] = ++n;
        init_seg(LC[u], l, l);
        init_seg(RC[u], r, r);
        merge(DP[LC[u]], DP[RC[u]], v[l], DP[u]);
    }
    else {
        int lmid = (2 * l + r) / 3;
        int rmid = (l + 2 * r) / 3;
        LC[u] = ++n;
        MC[u] = ++n;
        RC[u] = ++n;
        init_seg(LC[u], l, lmid);
        init_seg(MC[u], lmid + 1, rmid);
        init_seg(RC[u], rmid + 1, r);
        merge(DP[LC[u]], DP[MC[u]], v[lmid], DP[u]);
        merge(DP[u], DP[RC[u]], v[rmid], DP[u]);
    }

}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r = R;
    c = C;
    n = 1;

    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            h[i][j] = H[i][j];
            v[i][j] = V[i][j];
        }
    }

    init_seg(1, 0, r - 1);
}

void changeH(int u, int l, int r, int p) {
    if (l == r) {
        set_mono_dp(u, l);
    }
    else if (l + 1 == r) {
        if (l == p) {
            changeH(LC[u], l, l, p);
        }
        else {
            changeH(RC[u], r, r, p);
        }
        merge(DP[LC[u]], DP[RC[u]], v[l], DP[u]);
    }
    else {
        int lmid = (2 * l + r) / 3;
        int rmid = (l + 2 * r) / 3;
        if (p <= lmid) {
            changeH(LC[u], l, lmid, p);
        }
        else if (p <= rmid) {
            changeH(MC[u], lmid + 1, rmid, p);
        }
        else {
            changeH(RC[u], rmid + 1, r, p);
        }
        merge(DP[LC[u]], DP[MC[u]], v[lmid], DP[u]);
        merge(DP[u], DP[RC[u]], v[rmid], DP[u]);
    }
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    changeH(1, 0, r - 1, P);
}

void changeV(int u, int l, int r, int p) {
    if (l + 1 == r) {
        // then, l == p
        merge(DP[LC[u]], DP[RC[u]], v[l], DP[u]);
    }
    else {
        int lmid = (2 * l + r) / 3;
        int rmid = (l + 2 * r) / 3;
        if (p < lmid) {
            changeV(LC[u], l, lmid, p);
        }
        else if (p > lmid && p < rmid) {
            changeV(MC[u], lmid + 1, rmid, p);
        }
        else if (p > rmid) {
            changeV(RC[u], rmid + 1, r, p);
        }
        merge(DP[LC[u]], DP[MC[u]], v[lmid], DP[u]);
        merge(DP[u], DP[RC[u]], v[rmid], DP[u]);
    }
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;
    changeV(1, 0, r - 1, P);
}

int escape(int V1, int V2) {
    return DP[1][V1][V2];
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47828 KB Output is correct
2 Correct 19 ms 47804 KB Output is correct
3 Correct 70 ms 50552 KB Output is correct
4 Correct 20 ms 47828 KB Output is correct
5 Correct 19 ms 47768 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 54 ms 3368 KB Output is correct
12 Correct 1 ms 980 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 13712 KB Output is correct
2 Correct 46 ms 13524 KB Output is correct
3 Correct 84 ms 13924 KB Output is correct
4 Correct 69 ms 13884 KB Output is correct
5 Correct 70 ms 13708 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 215 ms 13876 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 57940 KB Output is correct
2 Correct 23 ms 58068 KB Output is correct
3 Correct 23 ms 57932 KB Output is correct
4 Correct 57 ms 59308 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 13652 KB Output is correct
2 Correct 46 ms 13640 KB Output is correct
3 Correct 80 ms 13932 KB Output is correct
4 Correct 69 ms 13908 KB Output is correct
5 Correct 83 ms 13812 KB Output is correct
6 Correct 23 ms 57940 KB Output is correct
7 Correct 22 ms 57916 KB Output is correct
8 Correct 22 ms 57920 KB Output is correct
9 Correct 50 ms 59292 KB Output is correct
10 Correct 23 ms 47828 KB Output is correct
11 Correct 19 ms 47788 KB Output is correct
12 Correct 70 ms 50564 KB Output is correct
13 Correct 19 ms 47840 KB Output is correct
14 Correct 18 ms 47732 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 312 KB Output is correct
18 Correct 1 ms 980 KB Output is correct
19 Correct 1 ms 980 KB Output is correct
20 Correct 1 ms 1084 KB Output is correct
21 Correct 1 ms 1080 KB Output is correct
22 Correct 1 ms 952 KB Output is correct
23 Correct 1 ms 980 KB Output is correct
24 Correct 1 ms 980 KB Output is correct
25 Correct 53 ms 3392 KB Output is correct
26 Correct 1 ms 980 KB Output is correct
27 Correct 219 ms 13924 KB Output is correct
28 Runtime error 293 ms 262144 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 13684 KB Output is correct
2 Correct 48 ms 13628 KB Output is correct
3 Correct 89 ms 13924 KB Output is correct
4 Correct 69 ms 13848 KB Output is correct
5 Correct 70 ms 13764 KB Output is correct
6 Correct 22 ms 57988 KB Output is correct
7 Correct 23 ms 57928 KB Output is correct
8 Correct 22 ms 57940 KB Output is correct
9 Correct 49 ms 59340 KB Output is correct
10 Correct 19 ms 47720 KB Output is correct
11 Correct 20 ms 47828 KB Output is correct
12 Correct 73 ms 50488 KB Output is correct
13 Correct 19 ms 47804 KB Output is correct
14 Correct 19 ms 47728 KB Output is correct
15 Runtime error 418 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -