제출 #555847

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
555847		blue	웜뱃 (IOI13_wombats)	C++17	100 / 100	10974 ms	117032 KiB

wombats

#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];
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24