oj.uz

Submission #614155

# Submission time Handle Problem Language Result Execution time Memory
614155 2022-07-30T20:19:52 Z keta_tsimakuridze Wombats (IOI13_wombats) C++14
76 / 100
 2437 ms 102644 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;
            c.d[i][j] = INF;
            if(j < C) {
                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 548 ms 97076 KB Output is correct
2 Correct 574 ms 97088 KB Output is correct
3 Correct 697 ms 98584 KB Output is correct
4 Correct 586 ms 97156 KB Output is correct
5 Correct 576 ms 97088 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 2 ms 2516 KB Output is correct
6 Correct 2 ms 2516 KB Output is correct
7 Correct 2 ms 2516 KB Output is correct
8 Correct 2 ms 2516 KB Output is correct
9 Correct 2 ms 2516 KB Output is correct
10 Correct 2 ms 2516 KB Output is correct
11 Correct 75 ms 3608 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 228 ms 5204 KB Output is correct
2 Correct 166 ms 5304 KB Output is correct
3 Correct 252 ms 5308 KB Output is correct
4 Correct 230 ms 5308 KB Output is correct
5 Correct 227 ms 5312 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 2 ms 1236 KB Output is correct
8 Correct 2 ms 1236 KB Output is correct
9 Correct 826 ms 5304 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 568 ms 100872 KB Output is correct
2 Correct 528 ms 101124 KB Output is correct
3 Correct 606 ms 101120 KB Output is correct
4 Correct 556 ms 101772 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 5300 KB Output is correct
2 Correct 166 ms 5304 KB Output is correct
3 Correct 244 ms 5304 KB Output is correct
4 Correct 277 ms 5332 KB Output is correct
5 Correct 233 ms 5204 KB Output is correct
6 Correct 575 ms 101000 KB Output is correct
7 Correct 545 ms 101084 KB Output is correct
8 Correct 514 ms 100932 KB Output is correct
9 Correct 625 ms 101720 KB Output is correct
10 Correct 528 ms 97004 KB Output is correct
11 Correct 517 ms 97088 KB Output is correct
12 Correct 695 ms 98672 KB Output is correct
13 Correct 592 ms 97088 KB Output is correct
14 Correct 520 ms 97084 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 2 ms 2516 KB Output is correct
20 Correct 3 ms 2516 KB Output is correct
21 Correct 2 ms 2516 KB Output is correct
22 Correct 2 ms 2516 KB Output is correct
23 Correct 3 ms 2516 KB Output is correct
24 Correct 2 ms 2516 KB Output is correct
25 Correct 66 ms 3540 KB Output is correct
26 Correct 2 ms 2516 KB Output is correct
27 Correct 835 ms 5308 KB Output is correct
28 Correct 2233 ms 101440 KB Output is correct
29 Correct 2437 ms 98228 KB Output is correct
30 Correct 2402 ms 98700 KB Output is correct
31 Correct 2206 ms 102644 KB Output is correct
32 Correct 1 ms 1492 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 5296 KB Output is correct
2 Correct 171 ms 5304 KB Output is correct
3 Correct 253 ms 5312 KB Output is correct
4 Correct 258 ms 5308 KB Output is correct
5 Correct 227 ms 5308 KB Output is correct
6 Correct 606 ms 100988 KB Output is correct
7 Correct 532 ms 100924 KB Output is correct
8 Correct 543 ms 101128 KB Output is correct
9 Correct 622 ms 101688 KB Output is correct
10 Correct 545 ms 97080 KB Output is correct
11 Correct 528 ms 97080 KB Output is correct
12 Correct 587 ms 98620 KB Output is correct
13 Correct 554 ms 97080 KB Output is correct
14 Correct 569 ms 97156 KB Output is correct
15 Incorrect 2220 ms 101232 KB Output isn't correct
16 Halted 0 ms 0 KB -