oj.uz

Submission #765891

# Submission time Handle Problem Language Result Execution time Memory
765891 2023-06-25T07:06:40 Z fefe Wombats (IOI13_wombats) C++17
100 / 100
 5675 ms 105220 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;

const int inf = 0x3fffffff;

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

// seg_tree
struct node {
    int dp[200][200];
    node *l, *r;
    node(){}

}*root;

// 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(int i, int A[200][200]) {
    for (int s = 0; s < c; s++) {
        A[s][s] = 0;
        for (int e = s + 1; e < c; e++) {
            A[s][e] = A[s][e - 1] + h[i][e - 1];
            A[e][s] = A[s][e];
        }
    }
}

int tmp[200][200];
void calc(node *u, int l, int r) {
    set_mono(l, u -> dp);
    for (int i = l + 1; i <= r; i++) {
        set_mono(i, tmp);
        merge(u -> dp, tmp, v[i - 1], u -> dp);
    }
}

void init_seg(node *u, int l, int r) {
    if (r - l <= 20) {
        calc(u, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    if (u -> l == NULL) u -> l = new node();
    if (u -> r == NULL) u -> r = new node();

    init_seg(u -> l, l, mid);
    init_seg(u -> r, mid + 1, r);
    merge(u -> l -> dp, u -> r -> dp, v[mid], u -> dp);
}

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

    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];
        }
    }
    root = new node();
    init_seg(root, 0, r - 1);
}

void update(node *u, int l, int r, int p) {
    if (r - l <= 20) {
        calc(u, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    if (p <= mid) {
        update(u -> l, l, mid, p);
    }
    else {
        update(u -> r, mid + 1, r, p);
    }
    merge(u -> l -> dp, u -> r -> dp, v[mid], u -> dp);
}

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


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

int escape(int V1, int V2) {
    return root -> dp[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 8 ms 15316 KB Output is correct
2 Correct 8 ms 15316 KB Output is correct
3 Correct 59 ms 16972 KB Output is correct
4 Correct 8 ms 15316 KB Output is correct
5 Correct 8 ms 15300 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 312 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 448 KB Output is correct
5 Correct 1 ms 444 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 53 ms 1472 KB Output is correct
12 Correct 1 ms 468 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 2196 KB Output is correct
2 Correct 89 ms 2132 KB Output is correct
3 Correct 141 ms 2200 KB Output is correct
4 Correct 136 ms 2196 KB Output is correct
5 Correct 125 ms 2248 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 312 KB Output is correct
9 Correct 428 ms 2112 KB Output is correct
10 Correct 1 ms 308 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19264 KB Output is correct
2 Correct 9 ms 19208 KB Output is correct
3 Correct 10 ms 19196 KB Output is correct
4 Correct 36 ms 20096 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 2188 KB Output is correct
2 Correct 91 ms 2172 KB Output is correct
3 Correct 126 ms 2128 KB Output is correct
4 Correct 127 ms 2192 KB Output is correct
5 Correct 123 ms 2132 KB Output is correct
6 Correct 10 ms 19284 KB Output is correct
7 Correct 10 ms 19156 KB Output is correct
8 Correct 10 ms 19268 KB Output is correct
9 Correct 36 ms 20040 KB Output is correct
10 Correct 8 ms 15316 KB Output is correct
11 Correct 8 ms 15316 KB Output is correct
12 Correct 63 ms 16992 KB Output is correct
13 Correct 8 ms 15300 KB Output is correct
14 Correct 8 ms 15316 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 312 KB Output is correct
17 Correct 0 ms 312 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 448 KB Output is correct
25 Correct 54 ms 1600 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 420 ms 2184 KB Output is correct
28 Correct 1139 ms 58564 KB Output is correct
29 Correct 1280 ms 55740 KB Output is correct
30 Correct 1275 ms 55840 KB Output is correct
31 Correct 1163 ms 59600 KB Output is correct
32 Correct 0 ms 340 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 2108 KB Output is correct
2 Correct 90 ms 2092 KB Output is correct
3 Correct 127 ms 2204 KB Output is correct
4 Correct 127 ms 2196 KB Output is correct
5 Correct 127 ms 2192 KB Output is correct
6 Correct 13 ms 19156 KB Output is correct
7 Correct 10 ms 19156 KB Output is correct
8 Correct 14 ms 19268 KB Output is correct
9 Correct 37 ms 20036 KB Output is correct
10 Correct 8 ms 15316 KB Output is correct
11 Correct 9 ms 15316 KB Output is correct
12 Correct 61 ms 16980 KB Output is correct
13 Correct 8 ms 15316 KB Output is correct
14 Correct 8 ms 15300 KB Output is correct
15 Correct 1482 ms 98288 KB Output is correct
16 Correct 5675 ms 99896 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 436 KB Output is correct
24 Correct 1 ms 444 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 53 ms 2808 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 423 ms 2204 KB Output is correct
30 Correct 1127 ms 62492 KB Output is correct
31 Correct 4510 ms 104568 KB Output is correct
32 Correct 4467 ms 104768 KB Output is correct
33 Correct 1275 ms 59212 KB Output is correct
34 Correct 4906 ms 101824 KB Output is correct
35 Correct 1360 ms 59280 KB Output is correct
36 Correct 4994 ms 101704 KB Output is correct
37 Correct 1230 ms 64084 KB Output is correct
38 Correct 5222 ms 105220 KB Output is correct
39 Correct 1 ms 312 KB Output is correct
40 Correct 5221 ms 101592 KB Output is correct