oj.uz

Submission #614184

# Submission time Handle Problem Language Result Execution time Memory
614184 2022-07-30T21:18:46 Z keta_tsimakuridze Wombats (IOI13_wombats) C++14
100 / 100
 8899 ms 112288 KB 
#include "wombats.h"
#include <bits/stdc++.h>
#define ll int
using namespace std;
const int ROW = 5002, COL = 202, B = 20;
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 566 ms 97096 KB Output is correct
2 Correct 568 ms 97112 KB Output is correct
3 Correct 660 ms 99004 KB Output is correct
4 Correct 606 ms 97116 KB Output is correct
5 Correct 545 ms 97112 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 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 2 ms 2516 KB Output is correct
5 Correct 3 ms 2516 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2516 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2516 KB Output is correct
10 Correct 2 ms 2516 KB Output is correct
11 Correct 68 ms 3792 KB Output is correct
12 Correct 2 ms 2516 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 5400 KB Output is correct
2 Correct 164 ms 5368 KB Output is correct
3 Correct 230 ms 5408 KB Output is correct
4 Correct 240 ms 5388 KB Output is correct
5 Correct 228 ms 5396 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 787 ms 5392 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 578 ms 101020 KB Output is correct
2 Correct 544 ms 101156 KB Output is correct
3 Correct 595 ms 101096 KB Output is correct
4 Correct 627 ms 102040 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 5324 KB Output is correct
2 Correct 189 ms 5368 KB Output is correct
3 Correct 230 ms 5396 KB Output is correct
4 Correct 281 ms 5392 KB Output is correct
5 Correct 218 ms 5388 KB Output is correct
6 Correct 528 ms 101064 KB Output is correct
7 Correct 555 ms 101008 KB Output is correct
8 Correct 564 ms 101068 KB Output is correct
9 Correct 633 ms 101992 KB Output is correct
10 Correct 594 ms 97104 KB Output is correct
11 Correct 537 ms 97136 KB Output is correct
12 Correct 600 ms 98880 KB Output is correct
13 Correct 588 ms 97020 KB Output is correct
14 Correct 557 ms 97108 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 2516 KB Output is correct
19 Correct 3 ms 2644 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2608 KB Output is correct
22 Correct 2 ms 2516 KB Output is correct
23 Correct 2 ms 2516 KB Output is correct
24 Correct 2 ms 2616 KB Output is correct
25 Correct 66 ms 3784 KB Output is correct
26 Correct 3 ms 2516 KB Output is correct
27 Correct 789 ms 5384 KB Output is correct
28 Correct 2202 ms 101676 KB Output is correct
29 Correct 2318 ms 98548 KB Output is correct
30 Correct 2425 ms 98800 KB Output is correct
31 Correct 2129 ms 102652 KB Output is correct
32 Correct 1 ms 1620 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 5380 KB Output is correct
2 Correct 166 ms 5376 KB Output is correct
3 Correct 239 ms 5392 KB Output is correct
4 Correct 236 ms 5384 KB Output is correct
5 Correct 224 ms 5396 KB Output is correct
6 Correct 548 ms 101196 KB Output is correct
7 Correct 520 ms 101172 KB Output is correct
8 Correct 564 ms 101124 KB Output is correct
9 Correct 593 ms 102000 KB Output is correct
10 Correct 536 ms 97268 KB Output is correct
11 Correct 581 ms 97108 KB Output is correct
12 Correct 601 ms 98912 KB Output is correct
13 Correct 588 ms 97184 KB Output is correct
14 Correct 549 ms 97112 KB Output is correct
15 Correct 2235 ms 101648 KB Output is correct
16 Correct 8899 ms 112288 KB Output is correct
17 Correct 1 ms 1236 KB Output is correct
18 Correct 1 ms 1204 KB Output is correct
19 Correct 1 ms 1236 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2516 KB Output is correct
22 Correct 2 ms 2612 KB Output is correct
23 Correct 2 ms 2644 KB Output is correct
24 Correct 2 ms 2516 KB Output is correct
25 Correct 2 ms 2516 KB Output is correct
26 Correct 2 ms 2644 KB Output is correct
27 Correct 68 ms 4868 KB Output is correct
28 Correct 2 ms 2516 KB Output is correct
29 Correct 783 ms 5388 KB Output is correct
30 Correct 2065 ms 105180 KB Output is correct
31 Correct 7194 ms 109680 KB Output is correct
32 Correct 7167 ms 109912 KB Output is correct
33 Correct 2378 ms 101768 KB Output is correct
34 Correct 7520 ms 106060 KB Output is correct
35 Correct 2340 ms 102092 KB Output is correct
36 Correct 7595 ms 106396 KB Output is correct
37 Correct 2153 ms 106760 KB Output is correct
38 Correct 6943 ms 110408 KB Output is correct
39 Correct 1 ms 1620 KB Output is correct
40 Correct 7674 ms 106172 KB Output is correct