oj.uz

Submission #555847

# Submission time Handle Problem Language Result Execution time Memory
555847 2022-05-01T16:51:51 Z blue Wombats (IOI13_wombats) C++17
100 / 100
 10974 ms 117032 KB 
#include "wombats.h"
#include <vector>
#include <algorithm>
#include <set>
#include <iostream>
#include <map>
using namespace std;

using vi = vector<int>;

const int rmx = 5000;
const int cmx = 200;

const int leaflim = 20;

int R, C;
int H[rmx][cmx], V[rmx][cmx];

const int INF = 2'000'000'001;

struct info
{
    int r1, r2;
    int a[cmx][cmx];

    info()
    {
        ;
    }
};



info combine(info A, info B)
{
    // cerr << "combine called\n";
    info res;

    vi old_barriers(C+2);
    vi new_barriers(C+2);

    old_barriers[0] = 0;
    old_barriers[1] = C-1;

    // cerr << "C = " << C << '\n';

    for(int vmu = C-1; vmu >= 0; vmu--)
    {
        new_barriers[0] = 0;

        int mxid;

        // cerr << "\n\n\n";
        // cerr << "vmu = " << vmu << '\n';

        for(int v = max(vmu, 0); v <= C-1 && v-vmu <= C-1; v++)
        {
            int u = v-vmu;

            // cerr << u << ' ' << v << '\n';

            res.a[u][v] = INF;

            int id = v - max(vmu, 0);

            for(int i = old_barriers[id]; i <= old_barriers[id+1]; i++)
            {
                int currcost = A.a[u][i] + V[A.r2][i] + B.a[i][v];

                if(currcost < res.a[u][v])
                {
                    res.a[u][v] = currcost;
                    new_barriers[id+1] = i;
                    // cerr << "new barrier = " << i << '\n';
                }
            }

           mxid = id;
        }

        // cerr << "old barriers = ";
        // for(int z = 0; z <= mxid+1; z++)
        //     cerr << old_barriers[z] << ' ';
        // cerr << '\n';

        new_barriers[mxid+1 + 1] = C-1;

        old_barriers = new_barriers;
    }


    old_barriers[0] = 0;
    old_barriers[1] = C-1;

    for(int vmu = -(C-1); vmu < 0; vmu++)
    {
        new_barriers[0] = 0;

        int mxid;

        // cerr << "\n\n\n";
        // cerr << "vmu = " << vmu << '\n';

        for(int v = max(vmu, 0); v <= C-1 && v-vmu <= C-1; v++)
        {
            int u = v-vmu;

            // cerr << u << ' ' << v << '\n';

            res.a[u][v] = INF;

            int id = v - max(vmu, 0);

            for(int i = old_barriers[id]; i <= old_barriers[id+1]; i++)
            {
                int currcost = A.a[u][i] + V[A.r2][i] + B.a[i][v];

                if(currcost < res.a[u][v])
                {
                    res.a[u][v] = currcost;
                    new_barriers[id+1] = i;
                    // cerr << "new barrier = " << i << '\n';
                }
            }

           mxid = id;
        }

        // cerr << "old barriers = ";
        // for(int z = 0; z <= mxid+1; z++)
        //     cerr << old_barriers[z] << ' ';
        // cerr << '\n';

        new_barriers[mxid+1 + 1] = C-1;

        old_barriers = new_barriers;
    }















    res.r1 = A.r1;
    res.r2 = B.r2;

    // cerr << "combine returned\n";

    return res;
}

info getinfo(int i1, int i2)
{
    // cerr << "getinfo " << i1 << ' ' << i2 << '\n';
    if(i1 == i2)
    {
        info res;

        res.r1 = i1;
        res.r2 = i2;

        for(int j1 = 0; j1 < C; j1++)
        {
            res.a[j1][j1] = 0;
            for(int j2 = j1+1; j2 < C; j2++)
                res.a[j1][j2] = res.a[j1][j2-1] + H[i1][j2-1];
            for(int j2 = j1-1; j2 >= 0; j2--)
                res.a[j1][j2] = res.a[j1][j2+1] + H[i1][j2];
        }
        // cerr << "return : " << i1 << '\n';
        return res;
    }
    else 
    {
        return combine(getinfo(i1, i2-1), getinfo(i2, i2));
    }
}


struct segtree
{
    info curr;

    segtree* left = NULL;
    segtree* right = NULL;

    segtree()
    {
        ;
    }

    segtree(int X, int Y)
    {
        // cerr << "build " << X << ' ' << Y << '\n';
        if(Y-X+1 <= leaflim)
        {
            curr = getinfo(X, Y);
        }
        else
        {
            int mid = (X+Y)/2;
            left = new segtree(X, mid);
            right = new segtree(mid+1, Y);
            curr = combine(left->curr, right->curr);
        }
    }

    void recompute(int I)
    {
        if(left == NULL)
            curr = getinfo(curr.r1, curr.r2);
        else
        {
            if(I <= (curr.r1+curr.r2)/2)
                left->recompute(I);
            else
                right->recompute(I);

            curr = combine(left->curr, right->curr);
        }
    }
};

segtree ST;

void init(int R_, int C_, int H_[5000][200], int V_[5000][200]) 
{
    R = R_;
    C = C_;
    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];
        }
    }

    // cerr << "init called\n";

    ST = segtree(0, R-1);

    // cerr << "answers = \n";

    // for(int j1 = 0; j1 < C; j1++)
    //     for(int j2 = 0; j2 < C; j2++)
    //         cerr << j1 << " -> " << j2 << " : " << ST.curr.a[j1][j2] << '\n';
}

void changeH(int P, int Q, int W) 
{
    H[P][Q] = W;
    ST.recompute(P);
}

void changeV(int P, int Q, int W) {
    V[P][Q] = W;
    ST.recompute(P);
    ST.recompute(P+1);
}

int escape(int V1, int V2) 
{
    return ST.curr.a[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 'info combine(info, info)':
wombats.cpp:134:29: warning: 'mxid' may be used uninitialized in this function [-Wmaybe-uninitialized]
  134 |         new_barriers[mxid+1 + 1] = C-1;
      |                      ~~~~~~~^~~
wombats.cpp:86:29: warning: 'mxid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |         new_barriers[mxid+1 + 1] = C-1;
      |                      ~~~~~~~^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1101 ms 101792 KB Output is correct
2 Correct 1066 ms 101896 KB Output is correct
3 Correct 1190 ms 104496 KB Output is correct
4 Correct 1106 ms 101912 KB Output is correct
5 Correct 1101 ms 101820 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Correct 1 ms 1348 KB Output is correct
8 Correct 1 ms 1364 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 4 ms 7124 KB Output is correct
5 Correct 5 ms 6996 KB Output is correct
6 Correct 4 ms 6996 KB Output is correct
7 Correct 5 ms 7048 KB Output is correct
8 Correct 4 ms 6740 KB Output is correct
9 Correct 6 ms 6740 KB Output is correct
10 Correct 4 ms 7068 KB Output is correct
11 Correct 67 ms 8028 KB Output is correct
12 Correct 4 ms 6996 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 8004 KB Output is correct
2 Correct 298 ms 7956 KB Output is correct
3 Correct 249 ms 7972 KB Output is correct
4 Correct 382 ms 7984 KB Output is correct
5 Correct 349 ms 7988 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Correct 1 ms 1364 KB Output is correct
9 Correct 924 ms 7960 KB Output is correct
10 Correct 1 ms 1748 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 902 ms 105696 KB Output is correct
2 Correct 1215 ms 105752 KB Output is correct
3 Correct 898 ms 105768 KB Output is correct
4 Correct 998 ms 107044 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 7884 KB Output is correct
2 Correct 314 ms 7956 KB Output is correct
3 Correct 199 ms 7892 KB Output is correct
4 Correct 381 ms 7972 KB Output is correct
5 Correct 287 ms 7972 KB Output is correct
6 Correct 880 ms 105772 KB Output is correct
7 Correct 1184 ms 105872 KB Output is correct
8 Correct 905 ms 105884 KB Output is correct
9 Correct 958 ms 107132 KB Output is correct
10 Correct 1070 ms 101820 KB Output is correct
11 Correct 1260 ms 101808 KB Output is correct
12 Correct 1187 ms 104520 KB Output is correct
13 Correct 1095 ms 101824 KB Output is correct
14 Correct 1143 ms 101856 KB Output is correct
15 Correct 1 ms 1364 KB Output is correct
16 Correct 1 ms 1364 KB Output is correct
17 Correct 1 ms 1348 KB Output is correct
18 Correct 4 ms 7124 KB Output is correct
19 Correct 4 ms 7124 KB Output is correct
20 Correct 4 ms 7124 KB Output is correct
21 Correct 5 ms 7124 KB Output is correct
22 Correct 4 ms 6740 KB Output is correct
23 Correct 4 ms 6740 KB Output is correct
24 Correct 4 ms 7124 KB Output is correct
25 Correct 67 ms 9412 KB Output is correct
26 Correct 4 ms 7112 KB Output is correct
27 Correct 970 ms 7964 KB Output is correct
28 Correct 2659 ms 110012 KB Output is correct
29 Correct 3111 ms 105716 KB Output is correct
30 Correct 2984 ms 105876 KB Output is correct
31 Correct 3071 ms 111592 KB Output is correct
32 Correct 2 ms 1748 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 7892 KB Output is correct
2 Correct 330 ms 7884 KB Output is correct
3 Correct 203 ms 7972 KB Output is correct
4 Correct 379 ms 7972 KB Output is correct
5 Correct 274 ms 7964 KB Output is correct
6 Correct 848 ms 105768 KB Output is correct
7 Correct 1106 ms 105752 KB Output is correct
8 Correct 860 ms 105824 KB Output is correct
9 Correct 938 ms 107168 KB Output is correct
10 Correct 1072 ms 101904 KB Output is correct
11 Correct 1066 ms 101872 KB Output is correct
12 Correct 1251 ms 104624 KB Output is correct
13 Correct 1250 ms 101708 KB Output is correct
14 Correct 1206 ms 101828 KB Output is correct
15 Correct 2356 ms 115432 KB Output is correct
16 Correct 9842 ms 117032 KB Output is correct
17 Correct 1 ms 1364 KB Output is correct
18 Correct 1 ms 1364 KB Output is correct
19 Correct 1 ms 1364 KB Output is correct
20 Correct 4 ms 7124 KB Output is correct
21 Correct 4 ms 7112 KB Output is correct
22 Correct 4 ms 7112 KB Output is correct
23 Correct 4 ms 7124 KB Output is correct
24 Correct 4 ms 6716 KB Output is correct
25 Correct 4 ms 6740 KB Output is correct
26 Correct 4 ms 7124 KB Output is correct
27 Correct 67 ms 9412 KB Output is correct
28 Correct 4 ms 7124 KB Output is correct
29 Correct 835 ms 7968 KB Output is correct
30 Correct 2443 ms 109908 KB Output is correct
31 Correct 7305 ms 114000 KB Output is correct
32 Correct 7682 ms 114080 KB Output is correct
33 Correct 2816 ms 105436 KB Output is correct
34 Correct 8475 ms 109832 KB Output is correct
35 Correct 2647 ms 105820 KB Output is correct
36 Correct 8402 ms 109756 KB Output is correct
37 Correct 3011 ms 111484 KB Output is correct
38 Correct 10974 ms 114620 KB Output is correct
39 Correct 2 ms 1748 KB Output is correct
40 Correct 10530 ms 109712 KB Output is correct