oj.uz

답안 #1068050

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1068050 2024-08-21T06:57:01 Z thinknoexit 웜뱃 (IOI13_wombats) C++17
55 / 100
 2641 ms 262144 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5050;
const int M = 101;
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 operator + (const A& o) const {
        A res;
        for (int i = 0;i < m;i++) {
            for (int j = 0;j < m;j++) {
                res.dis[i][j] = 1e9;
                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[(1 << 14) + 1];
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();
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 230996 KB Output is correct
2 Correct 106 ms 230772 KB Output is correct
3 Correct 142 ms 232432 KB Output is correct
4 Correct 111 ms 230996 KB Output is correct
5 Correct 127 ms 230948 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 1624 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 2 ms 1628 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 39 ms 2748 KB Output is correct
12 Correct 1 ms 1628 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 629 ms 9128 KB Output is correct
2 Correct 597 ms 8788 KB Output is correct
3 Correct 594 ms 9004 KB Output is correct
4 Correct 598 ms 9060 KB Output is correct
5 Correct 568 ms 9048 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2641 ms 9064 KB Output is correct
10 Correct 0 ms 604 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 110 ms 238800 KB Output is correct
2 Correct 108 ms 238740 KB Output is correct
3 Correct 110 ms 238672 KB Output is correct
4 Correct 131 ms 239456 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 629 ms 8796 KB Output is correct
2 Correct 603 ms 8988 KB Output is correct
3 Correct 604 ms 9064 KB Output is correct
4 Correct 596 ms 9060 KB Output is correct
5 Correct 576 ms 9044 KB Output is correct
6 Correct 113 ms 238836 KB Output is correct
7 Correct 131 ms 238648 KB Output is correct
8 Correct 108 ms 238672 KB Output is correct
9 Correct 134 ms 239700 KB Output is correct
10 Correct 107 ms 230992 KB Output is correct
11 Correct 114 ms 230736 KB Output is correct
12 Correct 140 ms 232572 KB Output is correct
13 Correct 124 ms 230840 KB Output is correct
14 Correct 106 ms 230996 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 2 ms 1628 KB Output is correct
19 Correct 2 ms 1628 KB Output is correct
20 Correct 1 ms 1628 KB Output is correct
21 Correct 1 ms 1628 KB Output is correct
22 Correct 1 ms 1624 KB Output is correct
23 Correct 1 ms 1628 KB Output is correct
24 Correct 1 ms 1628 KB Output is correct
25 Correct 40 ms 2644 KB Output is correct
26 Correct 1 ms 1628 KB Output is correct
27 Correct 2633 ms 9068 KB Output is correct
28 Runtime error 2527 ms 262144 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 602 ms 8784 KB Output is correct
2 Correct 584 ms 8992 KB Output is correct
3 Correct 603 ms 9064 KB Output is correct
4 Correct 601 ms 9012 KB Output is correct
5 Correct 591 ms 9064 KB Output is correct
6 Correct 134 ms 238712 KB Output is correct
7 Correct 115 ms 238676 KB Output is correct
8 Correct 112 ms 238800 KB Output is correct
9 Correct 151 ms 239444 KB Output is correct
10 Correct 140 ms 230992 KB Output is correct
11 Correct 109 ms 230736 KB Output is correct
12 Correct 178 ms 232528 KB Output is correct
13 Correct 127 ms 230996 KB Output is correct
14 Correct 112 ms 230940 KB Output is correct
15 Runtime error 134 ms 21052 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -