oj.uz

Submission #614185

# Submission time Handle Problem Language Result Execution time Memory
614185 2022-07-30T21:20:58 Z keta_tsimakuridze Wombats (IOI13_wombats) C++14
100 / 100
 6835 ms 184548 KB 
#include "wombats.h"
#include <bits/stdc++.h>
#define ll int
using namespace std;
const int ROW = 5002, COL = 202, B = 10;
int INF = 2e9;
int h[ROW][COL], v[ROW][COL],C,R;
struct node {
    ll d[COL][COL];
} tree[4 * ROW / 10];

node merge(node a, node b, int mid) {
    node c = a;
    vector<vector<int> > opt;
    opt.resize(C, vector<int>(C ));
    for(int i = 0; i < C; i++) {
        for(int j = 0; j < C; j++) {
            a.d[i][j] += v[mid][j];
        }
    }
    for(int i = 0; i < C; i++) {
        c.d[i][i] = INF;
        for(int j = 0; j < C; j++) {
            if(c.d[i][i] >= a.d[i][j] + b.d[j][i]) {
                opt[i][i] = j;
                c.d[i][i]= a.d[i][j] + b.d[j][i];
            }
        }
    }
    for(int X = 1; X < C; X++) {
        // i x j
        for(int i = 0; i < C; i++) {
            int j = i + X;

            if(j < C) { c.d[i][j] = INF;
                for(int k = opt[i][j - 1]; k <= opt[i + 1][j]; k++) {
                    if(c.d[i][j] >= a.d[i][k] + b.d[k][j]) {
                        c.d[i][j] = a.d[i][k] + b.d[k][j];
                        opt[i][j] = k;
                    }
                }
            }

            j = i - X;

            if(j >= 0) {
                c.d[i][j] = INF;
                for(int k = opt[i - 1][j]; k <= opt[i][j + 1]; k++) {
                    if(c.d[i][j] >= a.d[i][k] + b.d[k][j]) {
                        c.d[i][j] = a.d[i][k] + b.d[k][j];
                        opt[i][j] = k;
                    }
                }
            }
        }
    }
    return c;
}

node get(int l, int r) {
    if(l == r) {
        node a;
        for(int i = 0; i < C; i++) {
            a.d[i][i] = 0;
            for(int j = i + 1; j < C; j++) {
                a.d[i][j] = a.d[i][j - 1] + h[l][j - 1];
            }

            for(int j = i - 1; j >= 0; j--) {
                a.d[i][j] = a.d[i][j + 1] + h[l][j];
            }
        }
        return a;
    }
    int mid = (l + r) / 2;
    return merge(get(l, mid), get(mid + 1, r), mid);
}

void build(int u,int l, int r) {
    if(r - l + 1 <= B) {
        tree[u] = get(l, r);
        return;
    }
    int mid = (l + r)  / 2;
    build(2 * u, l, mid); build(2 * u + 1, mid + 1, r);

    tree[u] = merge(tree[2 * u], tree[2 * u + 1], mid);
}

void upd(int u,int id, int l, int r) {
    if(l > id || r < id) return;
    if(r - l + 1 <= B) {
        tree[u] = get(l, r);
        return;
    }
    int mid = (l + r) / 2;
    upd(2 * u, id, l, mid); upd(2 * u + 1, id, mid + 1, r);
    tree[u] = merge(tree[2 * u], tree[2 * u + 1], mid);
}

void init(int r, int c, int H[5000][200], int V[5000][200]) {
    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];
    }
    R = r; C = c; --R;
    build(1, 0, R);
}

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

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

int escape(int V1, int V2) {
    return tree[1].d[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 473 ms 178580 KB Output is correct
2 Correct 519 ms 178592 KB Output is correct
3 Correct 549 ms 180288 KB Output is correct
4 Correct 488 ms 178732 KB Output is correct
5 Correct 475 ms 178692 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 3 ms 2772 KB Output is correct
11 Correct 65 ms 3712 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 7704 KB Output is correct
2 Correct 113 ms 7700 KB Output is correct
3 Correct 161 ms 7700 KB Output is correct
4 Correct 156 ms 7704 KB Output is correct
5 Correct 144 ms 7640 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 540 ms 7716 KB Output is correct
10 Correct 1 ms 1620 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 182600 KB Output is correct
2 Correct 457 ms 182604 KB Output is correct
3 Correct 509 ms 182520 KB Output is correct
4 Correct 521 ms 183372 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 7696 KB Output is correct
2 Correct 117 ms 7624 KB Output is correct
3 Correct 158 ms 7636 KB Output is correct
4 Correct 155 ms 7708 KB Output is correct
5 Correct 173 ms 7756 KB Output is correct
6 Correct 454 ms 182616 KB Output is correct
7 Correct 515 ms 182676 KB Output is correct
8 Correct 498 ms 182560 KB Output is correct
9 Correct 558 ms 183472 KB Output is correct
10 Correct 479 ms 178692 KB Output is correct
11 Correct 482 ms 178688 KB Output is correct
12 Correct 550 ms 180228 KB Output is correct
13 Correct 513 ms 178700 KB Output is correct
14 Correct 488 ms 178688 KB Output is correct
15 Correct 1 ms 1236 KB Output is correct
16 Correct 1 ms 1236 KB Output is correct
17 Correct 1 ms 1236 KB Output is correct
18 Correct 2 ms 2772 KB Output is correct
19 Correct 2 ms 2772 KB Output is correct
20 Correct 2 ms 2772 KB Output is correct
21 Correct 2 ms 2772 KB Output is correct
22 Correct 3 ms 2784 KB Output is correct
23 Correct 2 ms 2772 KB Output is correct
24 Correct 2 ms 2772 KB Output is correct
25 Correct 67 ms 3752 KB Output is correct
26 Correct 2 ms 2772 KB Output is correct
27 Correct 550 ms 7700 KB Output is correct
28 Correct 1618 ms 182964 KB Output is correct
29 Correct 1801 ms 179884 KB Output is correct
30 Correct 1891 ms 180240 KB Output is correct
31 Correct 1774 ms 183960 KB Output is correct
32 Correct 1 ms 1492 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 7700 KB Output is correct
2 Correct 106 ms 7760 KB Output is correct
3 Correct 194 ms 7704 KB Output is correct
4 Correct 163 ms 7688 KB Output is correct
5 Correct 149 ms 7700 KB Output is correct
6 Correct 464 ms 182648 KB Output is correct
7 Correct 480 ms 182592 KB Output is correct
8 Correct 486 ms 182556 KB Output is correct
9 Correct 559 ms 183412 KB Output is correct
10 Correct 498 ms 178632 KB Output is correct
11 Correct 467 ms 178692 KB Output is correct
12 Correct 568 ms 180228 KB Output is correct
13 Correct 529 ms 178696 KB Output is correct
14 Correct 437 ms 178688 KB Output is correct
15 Correct 2328 ms 182908 KB Output is correct
16 Correct 6835 ms 184548 KB Output is correct
17 Correct 1 ms 1236 KB Output is correct
18 Correct 1 ms 1236 KB Output is correct
19 Correct 1 ms 1236 KB Output is correct
20 Correct 2 ms 2772 KB Output is correct
21 Correct 2 ms 2772 KB Output is correct
22 Correct 2 ms 2692 KB Output is correct
23 Correct 2 ms 2772 KB Output is correct
24 Correct 2 ms 2772 KB Output is correct
25 Correct 2 ms 2772 KB Output is correct
26 Correct 2 ms 2772 KB Output is correct
27 Correct 68 ms 3708 KB Output is correct
28 Correct 2 ms 2772 KB Output is correct
29 Correct 501 ms 7704 KB Output is correct
30 Correct 1636 ms 182912 KB Output is correct
31 Correct 5433 ms 183732 KB Output is correct
32 Correct 5445 ms 183612 KB Output is correct
33 Correct 1847 ms 179984 KB Output is correct
34 Correct 5668 ms 180520 KB Output is correct
35 Correct 1983 ms 180236 KB Output is correct
36 Correct 6080 ms 180636 KB Output is correct
37 Correct 1733 ms 184044 KB Output is correct
38 Correct 5314 ms 184160 KB Output is correct
39 Correct 1 ms 1620 KB Output is correct
40 Correct 6115 ms 180476 KB Output is correct