oj.uz

Submission #286585

# Submission time Handle Problem Language Result Execution time Memory
286585 2020-08-30T15:00:41 Z evpipis Wombats (IOI13_wombats) C++11
76 / 100
 20000 ms 30392 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][2];

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

        for (int i = 0; i < m; i++)
            for (int j = (i==0?0:opt[i-1][0]); 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][0] = opt[i][1] = j;
        for (int sz = 2; sz <= m; sz++){
            for (int a = 0, b = sz-1; b < m; a++, b++)
                for (int c = opt[a][0]; c <= opt[a+1][0]; 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][0] = c;

            for (int b = 0, a = sz-1; a < m; a++, b++)
                for (int c = opt[a][1]; c >= opt[a-1][1]; 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][1] = 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 = 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 1380 ms 20520 KB Output is correct
2 Correct 1379 ms 20500 KB Output is correct
3 Correct 1457 ms 22264 KB Output is correct
4 Correct 1393 ms 20580 KB Output is correct
5 Correct 1414 ms 20600 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 1664 KB Output is correct
5 Correct 2 ms 1664 KB Output is correct
6 Correct 2 ms 1664 KB Output is correct
7 Correct 2 ms 1664 KB Output is correct
8 Correct 2 ms 1664 KB Output is correct
9 Correct 2 ms 1664 KB Output is correct
10 Correct 2 ms 1664 KB Output is correct
11 Correct 84 ms 2680 KB Output is correct
12 Correct 3 ms 1664 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 3192 KB Output is correct
2 Correct 171 ms 3072 KB Output is correct
3 Correct 254 ms 3068 KB Output is correct
4 Correct 247 ms 2944 KB Output is correct
5 Correct 241 ms 2944 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 770 ms 3064 KB Output is correct
10 Correct 1 ms 1024 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1380 ms 28536 KB Output is correct
2 Correct 1410 ms 28536 KB Output is correct
3 Correct 1406 ms 28536 KB Output is correct
4 Correct 1465 ms 29432 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 3192 KB Output is correct
2 Correct 173 ms 3072 KB Output is correct
3 Correct 247 ms 2980 KB Output is correct
4 Correct 267 ms 2944 KB Output is correct
5 Correct 245 ms 2944 KB Output is correct
6 Correct 1391 ms 28584 KB Output is correct
7 Correct 1401 ms 28664 KB Output is correct
8 Correct 1396 ms 28536 KB Output is correct
9 Correct 1463 ms 29440 KB Output is correct
10 Correct 1427 ms 20472 KB Output is correct
11 Correct 1400 ms 20600 KB Output is correct
12 Correct 1523 ms 22008 KB Output is correct
13 Correct 1435 ms 20504 KB Output is correct
14 Correct 1415 ms 20504 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 1664 KB Output is correct
19 Correct 2 ms 1664 KB Output is correct
20 Correct 2 ms 1664 KB Output is correct
21 Correct 2 ms 1664 KB Output is correct
22 Correct 2 ms 1664 KB Output is correct
23 Correct 2 ms 1664 KB Output is correct
24 Correct 3 ms 1664 KB Output is correct
25 Correct 86 ms 2680 KB Output is correct
26 Correct 2 ms 1664 KB Output is correct
27 Correct 777 ms 2948 KB Output is correct
28 Correct 6522 ms 29440 KB Output is correct
29 Correct 8422 ms 25244 KB Output is correct
30 Correct 8563 ms 25180 KB Output is correct
31 Correct 6646 ms 30392 KB Output is correct
32 Correct 1 ms 1024 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 3108 KB Output is correct
2 Correct 178 ms 3072 KB Output is correct
3 Correct 256 ms 2944 KB Output is correct
4 Correct 247 ms 2948 KB Output is correct
5 Correct 245 ms 2952 KB Output is correct
6 Correct 1403 ms 28664 KB Output is correct
7 Correct 1690 ms 28536 KB Output is correct
8 Correct 1406 ms 28560 KB Output is correct
9 Correct 1437 ms 29312 KB Output is correct
10 Correct 1403 ms 20676 KB Output is correct
11 Correct 1372 ms 20504 KB Output is correct
12 Correct 1472 ms 22084 KB Output is correct
13 Correct 1398 ms 20604 KB Output is correct
14 Correct 1392 ms 20600 KB Output is correct
15 Correct 2174 ms 29156 KB Output is correct
16 Execution timed out 20042 ms 30072 KB Time limit exceeded
17 Halted 0 ms 0 KB -