oj.uz

Submission #765857

# Submission time Handle Problem Language Result Execution time Memory
765857 2023-06-25T06:38:06 Z fefe Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 38632 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[5200][200], v[5200][200];

// related with sqrt-decomposition
int block[73][200][200];
int res[200][200];
int bn;

// 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];
        }
    }
}

// array used in set_block function
int tmp[200][200];
void set_block(int idx) {
    int ed = min(r, idx * dr + dr);
    set_mono(idx * dr, block[idx]);
    for (int i = idx * dr + 1; i < ed; i++) {
        set_mono(i, tmp);
        merge(block[idx], tmp, v[i - 1], block[idx]);
    }
}

void copy_A_to_B(int A[200][200], int B[200][200]) {
    for (int i = 0; i < 200; i++) {
        for (int j = 0; j < 200; j++) {
            B[i][j] = A[i][j];
        }
    }
}
void get_res() {
    copy_A_to_B(block[0], res);
    for (int idx = 1; idx < bn; idx++) {
        merge(res, block[idx], v[idx * dr - 1], res);
    }

}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r = R;
    c = C;
    dr = sqrt(r);
    bn = r % dr ? r / dr + 1 : r / dr;

    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];
        }
    }
    
    for (int idx = 0; idx < bn; idx++) {
        set_block(idx);
    }
    get_res();
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    set_block(P / dr);
    get_res();
}


void changeV(int P, int Q, int W) {
    v[P][Q] = W;
    if (P % dr != dr - 1) {
        set_block(P / dr);
    }
    get_res();
}

int escape(int V1, int V2) {
    return res[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 12500 KB Output is correct
2 Correct 7 ms 12500 KB Output is correct
3 Correct 75 ms 14252 KB Output is correct
4 Correct 7 ms 12500 KB Output is correct
5 Correct 9 ms 12500 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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 53 ms 1660 KB Output is correct
12 Correct 1 ms 596 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 1928 KB Output is correct
2 Correct 92 ms 1920 KB Output is correct
3 Correct 154 ms 1864 KB Output is correct
4 Correct 141 ms 1824 KB Output is correct
5 Correct 164 ms 1748 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 0 ms 468 KB Output is correct
9 Correct 520 ms 1868 KB Output is correct
10 Correct 1 ms 468 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16524 KB Output is correct
2 Correct 10 ms 16468 KB Output is correct
3 Correct 11 ms 16468 KB Output is correct
4 Correct 38 ms 17188 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 1932 KB Output is correct
2 Correct 101 ms 1932 KB Output is correct
3 Correct 149 ms 1868 KB Output is correct
4 Correct 168 ms 1848 KB Output is correct
5 Correct 142 ms 1748 KB Output is correct
6 Correct 11 ms 16468 KB Output is correct
7 Correct 10 ms 16524 KB Output is correct
8 Correct 11 ms 16528 KB Output is correct
9 Correct 37 ms 17276 KB Output is correct
10 Correct 10 ms 12540 KB Output is correct
11 Correct 8 ms 12500 KB Output is correct
12 Correct 62 ms 14128 KB Output is correct
13 Correct 8 ms 12500 KB Output is correct
14 Correct 8 ms 12500 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 0 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 66 ms 1684 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 477 ms 1852 KB Output is correct
28 Correct 4149 ms 26400 KB Output is correct
29 Correct 4790 ms 22696 KB Output is correct
30 Correct 4828 ms 22700 KB Output is correct
31 Correct 3984 ms 28100 KB Output is correct
32 Correct 1 ms 468 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 1868 KB Output is correct
2 Correct 92 ms 1936 KB Output is correct
3 Correct 149 ms 1856 KB Output is correct
4 Correct 149 ms 1852 KB Output is correct
5 Correct 143 ms 1748 KB Output is correct
6 Correct 11 ms 16528 KB Output is correct
7 Correct 11 ms 16524 KB Output is correct
8 Correct 11 ms 16524 KB Output is correct
9 Correct 37 ms 17224 KB Output is correct
10 Correct 8 ms 12540 KB Output is correct
11 Correct 9 ms 12504 KB Output is correct
12 Correct 74 ms 14028 KB Output is correct
13 Correct 10 ms 12500 KB Output is correct
14 Correct 9 ms 12628 KB Output is correct
15 Correct 1535 ms 37592 KB Output is correct
16 Execution timed out 20048 ms 38632 KB Time limit exceeded
17 Halted 0 ms 0 KB -