oj.uz

Submission #286584

# Submission time Handle Problem Language Result Execution time Memory
286584 2020-08-30T14:52:41 Z evpipis Wombats (IOI13_wombats) C++11
76 / 100
 20000 ms 32648 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

const int len_n = 5005, len_m = 205, inf = 1e9+10;
int hor[len_n][len_m], ver[len_n][len_m], n, m, k;

struct{
    struct node{
        int to[len_m][len_m];

        node(){
            for (int a = 0; a < m; a++)
                for (int b = 0; b < m; b++)
                    to[a][b] = inf; // check this
        }

        node(int i){
            for (int a = 0, suma = 0; a < m; a++){
                for (int b = 0, dif = suma; b < m; b++){
                    to[a][b] = dif + ver[i][b];

                    if (b < a)
                        dif -= hor[i][b];
                    else
                        dif += hor[i][b];
                }

                suma += hor[i][a];
            }
        }
    };

    node buck[85], root, temp;
    int opt[len_m][len_m];

    node join(node &fir, node &sec){
        node res;

        for (int i = 0; i < m; i++)
            for (int j = (i==0?0:opt[i-1][i-1]); j < m; j++)
                if (fir.to[i][j]+sec.to[j][i] < res.to[i][i])
                    res.to[i][i] = fir.to[i][j]+sec.to[j][i], opt[i][i] = j;
        for (int sz = 2; sz <= m; sz++){
            for (int a = 0, b = sz-1; b < m; a++, b++)
                for (int c = opt[a][b-1]; c <= opt[a+1][b]; c++)
                    if (fir.to[a][c]+sec.to[c][b] < res.to[a][b])
                        res.to[a][b] = fir.to[a][c]+sec.to[c][b], opt[a][b] = c;

            for (int b = 0, a = sz-1; a < m; a++, b++)
                for (int c = opt[a][b+1]; c >= opt[a-1][b]; c--)
                    if (fir.to[a][c]+sec.to[c][b] < res.to[a][b])
                        res.to[a][b] = fir.to[a][c]+sec.to[c][b], opt[a][b] = c;
        }

        return res;
    }

    void upd_buck(int b){
        int st = b*k, en = min(n, (b+1)*k);

        buck[b] = node(st);
        for (int i = st+1; i < en; i++)
            temp = node(i), buck[b] = join(buck[b], temp);
    }

    void upd_root(){
        root = buck[0];
        for (int b = 1; b*k < n; b++)
            root = join(root, buck[b]);
    }

    int ask(int a, int b){
        return root.to[a][b];
    }
} data;

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n = R, m = C;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m-1; j++)
            hor[i][j] = H[i][j];
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < m; j++)
            ver[i][j] = V[i][j];

    k = 60; //sqrt(n);
    for (int b = 0; k*b < n; b++)
        data.upd_buck(b);
    data.upd_root();
}

void changeH(int P, int Q, int W) {
    hor[P][Q] = W;
    data.upd_buck(P/k);
    data.upd_root();
}

void changeV(int P, int Q, int W) {
    ver[P][Q] = W;
    data.upd_buck(P/k);
    data.upd_root();
}

int escape(int V1, int V2) {
    return data.ask(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;
      |      ^~~
wombats.cpp: In function 'void<unnamed struct>::upd_buck(int)':
wombats.cpp:64:18: warning: '<anonymous>' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |             temp = node(i), buck[b] = join(buck[b], temp);
      |             ~~~~~^~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1351 ms 22520 KB Output is correct
2 Correct 1358 ms 22520 KB Output is correct
3 Correct 1434 ms 24312 KB Output is correct
4 Correct 1354 ms 22520 KB Output is correct
5 Correct 1346 ms 22392 KB Output is correct
6 Correct 1 ms 896 KB Output is correct
7 Correct 1 ms 896 KB Output is correct
8 Correct 1 ms 896 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 1 ms 896 KB Output is correct
4 Correct 2 ms 1024 KB Output is correct
5 Correct 2 ms 1024 KB Output is correct
6 Correct 2 ms 1024 KB Output is correct
7 Correct 2 ms 1024 KB Output is correct
8 Correct 2 ms 1024 KB Output is correct
9 Correct 2 ms 928 KB Output is correct
10 Correct 2 ms 1024 KB Output is correct
11 Correct 85 ms 2168 KB Output is correct
12 Correct 2 ms 1024 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 1788 KB Output is correct
2 Correct 617 ms 1784 KB Output is correct
3 Correct 755 ms 1784 KB Output is correct
4 Correct 721 ms 1788 KB Output is correct
5 Correct 823 ms 1784 KB Output is correct
6 Correct 1 ms 896 KB Output is correct
7 Correct 1 ms 896 KB Output is correct
8 Correct 1 ms 896 KB Output is correct
9 Correct 3015 ms 1912 KB Output is correct
10 Correct 1 ms 896 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1356 ms 30472 KB Output is correct
2 Correct 1349 ms 30456 KB Output is correct
3 Correct 1351 ms 30584 KB Output is correct
4 Correct 1406 ms 31480 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 1784 KB Output is correct
2 Correct 616 ms 1784 KB Output is correct
3 Correct 759 ms 1792 KB Output is correct
4 Correct 731 ms 1784 KB Output is correct
5 Correct 817 ms 1784 KB Output is correct
6 Correct 1342 ms 30456 KB Output is correct
7 Correct 1364 ms 30328 KB Output is correct
8 Correct 1349 ms 30456 KB Output is correct
9 Correct 1426 ms 31352 KB Output is correct
10 Correct 1362 ms 22392 KB Output is correct
11 Correct 1357 ms 22520 KB Output is correct
12 Correct 1440 ms 24312 KB Output is correct
13 Correct 1350 ms 22600 KB Output is correct
14 Correct 1358 ms 22520 KB Output is correct
15 Correct 1 ms 896 KB Output is correct
16 Correct 1 ms 896 KB Output is correct
17 Correct 1 ms 896 KB Output is correct
18 Correct 2 ms 1024 KB Output is correct
19 Correct 2 ms 1024 KB Output is correct
20 Correct 2 ms 1024 KB Output is correct
21 Correct 2 ms 1024 KB Output is correct
22 Correct 2 ms 1024 KB Output is correct
23 Correct 2 ms 1024 KB Output is correct
24 Correct 2 ms 1024 KB Output is correct
25 Correct 86 ms 2168 KB Output is correct
26 Correct 2 ms 1024 KB Output is correct
27 Correct 3015 ms 1792 KB Output is correct
28 Correct 7232 ms 31480 KB Output is correct
29 Correct 8238 ms 26208 KB Output is correct
30 Correct 8445 ms 26136 KB Output is correct
31 Correct 7195 ms 32648 KB Output is correct
32 Correct 1 ms 896 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 1908 KB Output is correct
2 Correct 614 ms 1784 KB Output is correct
3 Correct 755 ms 1912 KB Output is correct
4 Correct 731 ms 1784 KB Output is correct
5 Correct 823 ms 1784 KB Output is correct
6 Correct 1354 ms 30588 KB Output is correct
7 Correct 1350 ms 30456 KB Output is correct
8 Correct 1367 ms 30664 KB Output is correct
9 Correct 1398 ms 31612 KB Output is correct
10 Correct 1339 ms 22564 KB Output is correct
11 Correct 1330 ms 22520 KB Output is correct
12 Correct 1424 ms 24312 KB Output is correct
13 Correct 1340 ms 22500 KB Output is correct
14 Correct 1365 ms 22520 KB Output is correct
15 Correct 2350 ms 31284 KB Output is correct
16 Execution timed out 20087 ms 32076 KB Time limit exceeded
17 Halted 0 ms 0 KB -