oj.uz

Submission #555849

# Submission time Handle Problem Language Result Execution time Memory
555849 2022-05-01T16:53:47 Z blue Wombats (IOI13_wombats) C++17
100 / 100
 6888 ms 186644 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 = 10;

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 702 ms 180892 KB Output is correct
2 Correct 744 ms 181036 KB Output is correct
3 Correct 857 ms 182496 KB Output is correct
4 Correct 716 ms 181008 KB Output is correct
5 Correct 691 ms 180892 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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1400 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 4436 KB Output is correct
5 Correct 3 ms 4436 KB Output is correct
6 Correct 4 ms 4436 KB Output is correct
7 Correct 3 ms 4436 KB Output is correct
8 Correct 4 ms 4436 KB Output is correct
9 Correct 3 ms 4436 KB Output is correct
10 Correct 3 ms 4436 KB Output is correct
11 Correct 68 ms 5392 KB Output is correct
12 Correct 3 ms 4388 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 8728 KB Output is correct
2 Correct 209 ms 8728 KB Output is correct
3 Correct 145 ms 8660 KB Output is correct
4 Correct 253 ms 8780 KB Output is correct
5 Correct 199 ms 8660 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 580 ms 8740 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 575 ms 184800 KB Output is correct
2 Correct 728 ms 184924 KB Output is correct
3 Correct 634 ms 184800 KB Output is correct
4 Correct 686 ms 185876 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 8732 KB Output is correct
2 Correct 182 ms 8656 KB Output is correct
3 Correct 138 ms 8732 KB Output is correct
4 Correct 247 ms 8728 KB Output is correct
5 Correct 212 ms 8780 KB Output is correct
6 Correct 587 ms 184804 KB Output is correct
7 Correct 691 ms 184840 KB Output is correct
8 Correct 576 ms 184912 KB Output is correct
9 Correct 623 ms 185736 KB Output is correct
10 Correct 764 ms 180812 KB Output is correct
11 Correct 707 ms 180940 KB Output is correct
12 Correct 777 ms 182568 KB Output is correct
13 Correct 726 ms 180932 KB Output is correct
14 Correct 732 ms 180896 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 1364 KB Output is correct
18 Correct 3 ms 4436 KB Output is correct
19 Correct 3 ms 4424 KB Output is correct
20 Correct 3 ms 4436 KB Output is correct
21 Correct 3 ms 4436 KB Output is correct
22 Correct 4 ms 4436 KB Output is correct
23 Correct 3 ms 4436 KB Output is correct
24 Correct 3 ms 4436 KB Output is correct
25 Correct 72 ms 5456 KB Output is correct
26 Correct 4 ms 4436 KB Output is correct
27 Correct 585 ms 8728 KB Output is correct
28 Correct 1660 ms 185172 KB Output is correct
29 Correct 1981 ms 181792 KB Output is correct
30 Correct 2045 ms 182016 KB Output is correct
31 Correct 2024 ms 186152 KB Output is correct
32 Correct 1 ms 1620 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 8728 KB Output is correct
2 Correct 173 ms 8744 KB Output is correct
3 Correct 131 ms 8732 KB Output is correct
4 Correct 229 ms 8824 KB Output is correct
5 Correct 176 ms 8732 KB Output is correct
6 Correct 489 ms 184792 KB Output is correct
7 Correct 637 ms 184808 KB Output is correct
8 Correct 527 ms 184932 KB Output is correct
9 Correct 588 ms 185552 KB Output is correct
10 Correct 645 ms 181008 KB Output is correct
11 Correct 677 ms 180812 KB Output is correct
12 Correct 666 ms 182432 KB Output is correct
13 Correct 671 ms 180948 KB Output is correct
14 Correct 613 ms 180896 KB Output is correct
15 Correct 1858 ms 184832 KB Output is correct
16 Correct 6888 ms 186644 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 3 ms 4436 KB Output is correct
21 Correct 3 ms 4436 KB Output is correct
22 Correct 3 ms 4436 KB Output is correct
23 Correct 2 ms 4436 KB Output is correct
24 Correct 3 ms 4468 KB Output is correct
25 Correct 3 ms 4436 KB Output is correct
26 Correct 3 ms 4436 KB Output is correct
27 Correct 66 ms 5440 KB Output is correct
28 Correct 3 ms 4436 KB Output is correct
29 Correct 525 ms 8724 KB Output is correct
30 Correct 1720 ms 185268 KB Output is correct
31 Correct 5123 ms 185552 KB Output is correct
32 Correct 5177 ms 185468 KB Output is correct
33 Correct 1956 ms 181760 KB Output is correct
34 Correct 6013 ms 182308 KB Output is correct
35 Correct 1997 ms 181944 KB Output is correct
36 Correct 6118 ms 182372 KB Output is correct
37 Correct 2048 ms 186228 KB Output is correct
38 Correct 6092 ms 186272 KB Output is correct
39 Correct 1 ms 1748 KB Output is correct
40 Correct 6436 ms 182208 KB Output is correct