oj.uz

Submission #1067833

# Submission time Handle Problem Language Result Execution time Memory
1067833 2024-08-21T04:11:24 Z thinknoexit Wombats (IOI13_wombats) C++17
39 / 100
 59 ms 78684 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5050;
const int M = 22;
int rc[N][M]; // cost from (i, j) -> (i+1, j)
int cc[N][M]; // cost from (i, j) -> (i, j+1)
int n, m;
struct A {
    int dis[M][M], r;
    A() { memset(dis, 0x3f, sizeof dis), r = 0; }
    A operator + (const A& o) const {
        A res;
        for (int i = 0;i < m;i++) {
            for (int j = 0;j < m;j++) {
                for (int k = 0;k < m;k++) {
                    res.dis[i][j] = min(res.dis[i][j],
                        dis[i][k] + rc[r][k] + o.dis[k][j]);
                }
            }
        }
        res.r = o.r;
        return res;
    }
} tree[4 * N];
void build(int now = 1, int l = 0, int r = n - 1) {
    if (l == r) {
        vector<int> sum(m);
        sum[0] = 0;
        for (int i = 1;i < m;i++) {
            sum[i] = sum[i - 1] + cc[l][i - 1];
        }
        for (int i = 0;i < m;i++) {
            for (int j = i;j < m;j++) {
                tree[now].dis[i][j] = tree[now].dis[j][i] = sum[j] - sum[i];
            }
        }
        tree[now].r = r;
        return;
    }
    int mid = (l + r) / 2;
    build(2 * now, l, mid), build(2 * now + 1, mid + 1, r);
    tree[now] = tree[2 * now] + tree[2 * now + 1];
};
void update(int v, int now = 1, int l = 0, int r = n - 1) {
    if (l == r) {
        vector<int> sum(m);
        sum[0] = 0;
        for (int i = 1;i < m;i++) {
            sum[i] = sum[i - 1] + cc[l][i - 1];
        }
        for (int i = 0;i < m;i++) {
            for (int j = i;j < m;j++) {
                tree[now].dis[i][j] = tree[now].dis[j][i] = sum[j] - sum[i];
            }
        }
        tree[now].r = r;
        return;
    }
    int mid = (l + r) / 2;
    if (v <= mid) update(v, 2 * now, l, mid);
    else update(v, 2 * now + 1, mid + 1, r);
    tree[now] = tree[2 * now] + tree[2 * now + 1];
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n = R, m = C;
    for (int i = 0;i < n - 1;i++) {
        for (int j = 0;j < m;j++) {
            rc[i][j] = V[i][j];
        }
    }
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m - 1;j++) {
            cc[i][j] = H[i][j];
        }
    }
    build();
    // for (int i = 0;i < m;i++) {
    //     for (int j = 0;j < m;j++) {
    //         cout << tree[4].dis[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
}

void changeH(int P, int Q, int W) {
    cc[P][Q] = W;
    update(P);
}

void changeV(int P, int Q, int W) {
    rc[P][Q] = W;
    update(P);
}

int escape(int V1, int V2) {
    return tree[1].dis[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 18 ms 43100 KB Output is correct
2 Correct 17 ms 43128 KB Output is correct
3 Correct 59 ms 44708 KB Output is correct
4 Correct 20 ms 43100 KB Output is correct
5 Correct 18 ms 43140 KB Output is correct
6 Correct 15 ms 38716 KB Output is correct
7 Correct 13 ms 38652 KB Output is correct
8 Correct 15 ms 38752 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 38748 KB Output is correct
2 Correct 14 ms 38792 KB Output is correct
3 Correct 16 ms 38744 KB Output is correct
4 Correct 15 ms 38748 KB Output is correct
5 Correct 15 ms 38772 KB Output is correct
6 Correct 14 ms 38748 KB Output is correct
7 Correct 15 ms 38656 KB Output is correct
8 Correct 20 ms 38600 KB Output is correct
9 Correct 16 ms 38748 KB Output is correct
10 Correct 13 ms 38748 KB Output is correct
11 Correct 49 ms 39724 KB Output is correct
12 Correct 16 ms 38744 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 78580 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47448 KB Output is correct
2 Correct 23 ms 47452 KB Output is correct
3 Correct 22 ms 47448 KB Output is correct
4 Correct 42 ms 48172 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 78672 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 78684 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -