Submission #413609

#	Time	Username	Problem	Language	Result	Execution time	Memory
413609		KoD	Wombats (IOI13_wombats)	C++17	27 / 100	81 ms	10548 KiB

wombats

#include <bits/stdc++.h>
#include "wombats.h"

template <class T> using Vec = std::vector<T>;

int Type, Vsum;
Vec<Vec<int>> vert, side;
Vec<std::array<std::array<int, 2>, 2>> pos;

struct SemiGroup {
    std::array<std::array<int, 2>, 2> dist;
    int right;

    SemiGroup operator + (const SemiGroup& other) const {
        std::array<std::array<int, 2>, 2> ret;
        for (auto& v: ret) {
            v.fill(1000000000);
        }
        for (int i = 0; i < 2; ++i) {
            for (int k = 0; k < 2; ++k) {
                for (int j = 0; j < 2; ++j) {
                    ret[i][j] = std::min(ret[i][j], dist[i][k] + vert[right][k] + other.dist[k][j]);
                }
            }
        }
        return SemiGroup { std::move(ret), other.right };
    }
};

using Monoid = std::optional<SemiGroup>;
constexpr Monoid zero() { return std::nullopt; }
Monoid operator + (const Monoid& l, const Monoid& r) {
    if (!l) return r;
    if (!r) return l;
    return *l + *r;
}

int ceil_log2(const int x) {
    int e = 0;
    while ((1 << e) < x) e += 1;
    return e;
}

struct Segtree {
    Vec<Monoid> data;
    Segtree() = default;
    Segtree(const int n): data(1 << (ceil_log2(n) + 1), zero()) {}
    void assign(int i, const Monoid& m) {
        i += data.size() / 2;
        data[i] = m;
        while (i > 1) {
            i >>= 1;
            data[i] = data[2 * i] + data[2 * i + 1];
        }
    }
    Monoid fold() { return data[1]; }
} seg;
 
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    vert = Vec<Vec<int>>(R - 1, Vec<int>(C));
    for (int i = 0; i < R - 1; ++i) {
        for (int j = 0; j < C; ++j) {
            vert[i][j] = V[i][j];
        }
    }
    side = Vec<Vec<int>>(R, Vec<int>(C - 1));
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C - 1; ++j) {
            side[i][j] = H[i][j];
        }
    }
    if (C == 1) {
        Type = 1;
        for (int i = 0; i < R - 1; ++i) {
            Vsum += vert[i][0];
        }
    }
    else if (C == 2) {
        Type = 2;
        seg = Segtree(R);
        pos.resize(R);
        for (int i = 0; i < R; ++i) {
            pos[i][0][0] = pos[i][1][1] = 0;
            pos[i][0][1] = pos[i][1][0] = side[i][0];
            seg.assign(i, SemiGroup{pos[i], i});
        }
    }
    else {
        Type = 3;
    }
}

void changeH(int P, int Q, int W) {
    if (Type == 2) {
        const int i = P;
        side[i][0] = W;
        pos[i][0][0] = pos[i][1][1] = 0;
        pos[i][0][1] = pos[i][1][0] = side[i][0];
        seg.assign(i, SemiGroup{pos[i], i});
    }
    else {

    }
}

void changeV(int P, int Q, int W) {
    if (Type == 1) {
        Vsum -= vert[P][Q];
        Vsum += W;
        vert[P][Q] = W;
    }
    else if (Type == 2) {
        vert[P][Q] = W;
        seg.assign(P, SemiGroup{pos[P], P});
    }
    else {

    }
}

int escape(int V1, int V2) {
    if (Type == 1) {
        return Vsum;
    }
    else if (Type == 2) {
        return seg.fold() -> dist[V1][V2];
    }
    else {

    }
}

Compilation message (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 'int escape(int, int)':
wombats.cpp:131:1: warning: control reaches end of non-void function [-Wreturn-type]
  131 | }
      | ^

• Subtask 1: 9 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24