oj.uz

Submission #286473

# Submission time Handle Problem Language Result Execution time Memory
286473 2020-08-30T12:57:31 Z evpipis Wombats (IOI13_wombats) C++11
55 / 100
 20000 ms 29912 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[75], root;

    node join(node fir, node sec){
        node res;
        queue<tuple<int, int, int, int> > myq;
        for (int a = 0; a < m; a++){
            myq.push(make_tuple(0, m-1, 0, m-1));
            while (!myq.empty()){
                tuple<int, int, int, int> fron = myq.front();
                myq.pop();

                int l = get<0>(fron), r = get<1>(fron), o1 = get<2>(fron), o2 = get<3>(fron);
                int b = (l+r)/2, opt;
                for (int c = o1; c <= o2; 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 = c;

                if (l < b)
                    myq.push(make_tuple(l, b-1, o1, opt));
                if (b < r)
                    myq.push(make_tuple(b+1, r, opt, o2));
            }
        }

        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++)
            buck[b] = join(buck[b], node(i));
    }

    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;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2895 ms 20992 KB Output is correct
2 Correct 2853 ms 21112 KB Output is correct
3 Correct 2976 ms 22532 KB Output is correct
4 Correct 2874 ms 20992 KB Output is correct
5 Correct 2859 ms 21088 KB Output is correct
6 Correct 1 ms 1152 KB Output is correct
7 Correct 1 ms 1152 KB Output is correct
8 Correct 1 ms 1152 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1128 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Correct 3 ms 2176 KB Output is correct
5 Correct 3 ms 2176 KB Output is correct
6 Correct 3 ms 2176 KB Output is correct
7 Correct 3 ms 2176 KB Output is correct
8 Correct 3 ms 2176 KB Output is correct
9 Correct 3 ms 2176 KB Output is correct
10 Correct 3 ms 2048 KB Output is correct
11 Correct 95 ms 3192 KB Output is correct
12 Correct 3 ms 2176 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 913 ms 3600 KB Output is correct
2 Correct 718 ms 3608 KB Output is correct
3 Correct 918 ms 3444 KB Output is correct
4 Correct 945 ms 3448 KB Output is correct
5 Correct 911 ms 3436 KB Output is correct
6 Correct 1 ms 1152 KB Output is correct
7 Correct 1 ms 1152 KB Output is correct
8 Correct 1 ms 1152 KB Output is correct
9 Correct 3462 ms 3448 KB Output is correct
10 Correct 2 ms 1408 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2882 ms 28916 KB Output is correct
2 Correct 2887 ms 28924 KB Output is correct
3 Correct 2918 ms 28920 KB Output is correct
4 Correct 3001 ms 29736 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 989 ms 3704 KB Output is correct
2 Correct 723 ms 3576 KB Output is correct
3 Correct 915 ms 3448 KB Output is correct
4 Correct 929 ms 3448 KB Output is correct
5 Correct 914 ms 3448 KB Output is correct
6 Correct 3113 ms 28912 KB Output is correct
7 Correct 2887 ms 29008 KB Output is correct
8 Correct 2871 ms 29048 KB Output is correct
9 Correct 2926 ms 29724 KB Output is correct
10 Correct 2968 ms 21068 KB Output is correct
11 Correct 2845 ms 20996 KB Output is correct
12 Correct 2968 ms 22648 KB Output is correct
13 Correct 2871 ms 20988 KB Output is correct
14 Correct 2885 ms 21112 KB Output is correct
15 Correct 1 ms 1152 KB Output is correct
16 Correct 1 ms 1152 KB Output is correct
17 Correct 1 ms 1152 KB Output is correct
18 Correct 3 ms 2176 KB Output is correct
19 Correct 3 ms 2176 KB Output is correct
20 Correct 3 ms 2176 KB Output is correct
21 Correct 3 ms 2176 KB Output is correct
22 Correct 3 ms 2048 KB Output is correct
23 Correct 3 ms 2176 KB Output is correct
24 Correct 3 ms 2176 KB Output is correct
25 Correct 100 ms 3192 KB Output is correct
26 Correct 3 ms 2176 KB Output is correct
27 Correct 3481 ms 3320 KB Output is correct
28 Execution timed out 20073 ms 29876 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 923 ms 3832 KB Output is correct
2 Correct 722 ms 3592 KB Output is correct
3 Correct 910 ms 3448 KB Output is correct
4 Correct 926 ms 3448 KB Output is correct
5 Correct 914 ms 3448 KB Output is correct
6 Correct 2888 ms 29036 KB Output is correct
7 Correct 2900 ms 29048 KB Output is correct
8 Correct 2929 ms 28924 KB Output is correct
9 Correct 2951 ms 29912 KB Output is correct
10 Correct 2879 ms 21112 KB Output is correct
11 Correct 2826 ms 21112 KB Output is correct
12 Correct 2952 ms 22648 KB Output is correct
13 Correct 2854 ms 21112 KB Output is correct
14 Correct 2873 ms 21120 KB Output is correct
15 Correct 8654 ms 29696 KB Output is correct
16 Execution timed out 20066 ms 29812 KB Time limit exceeded
17 Halted 0 ms 0 KB -