Submission #413613

#	Time	Username	Problem	Language	Result	Execution time	Memory
413613		KoD	Wombats (IOI13_wombats)	C++17	39 / 100	20095 ms	26164 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 if (R <= 20 and C <= 20) {
        Type = 3;
    }
    else {
        Type = 4;
    }
}

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 {
        side[P][Q] = W;
    }
}

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 {
        vert[P][Q] = W;
    }
}

int escape(int V1, int V2) {
    if (Type == 1) {
        return Vsum;
    }
    else if (Type == 2) {
        return seg.fold() -> dist[V1][V2];
    }
    else if (Type == 3) {
        static Vec<Vec<int>> dist;
        static bool first = true;
        if (first) {
            const int R = (int) side.size();
            const int C = (int) side[0].size() + 1;
            dist = Vec<Vec<int>>(C, Vec<int>(C));
            for (int i = 0; i < C; ++i) {
                int sum = 0;
                for (int j = i; j < C; ++j) {
                    dist[i][j] = dist[j][i] = sum;
                    if (j != C - 1) {
                        sum += side[0][j];
                    }
                }
            }
            for (int i = 0; i < R - 1; ++i) {
                Vec<Vec<int>> merge(C, Vec<int>(C));
                for (int j = 0; j < C; ++j) {
                    int sum = 0;
                    for (int k = j; k < C; ++k) {
                        merge[j][k] = merge[k][j] = sum;
                        if (k != C - 1) {
                            sum += side[i + 1][k];
                        }
                    }
                }
                Vec<Vec<int>> next(C, Vec<int>(C, 1000000000));
                for (int j = 0; j < C; ++j) {
                    for (int k = 0; k < C; ++k) {
                        for (int l = 0; l < C; ++l) {
                            next[j][l] = std::min(next[j][l], dist[j][k] + vert[i][k] + merge[k][l]);
                        }
                    }
                }
                dist = std::move(next);
            }
            first = false;
        }
        return dist[V1][V2];
    }
    else {
        const int R = (int) side.size();
        const int C = (int) side[0].size() + 1;
        Vec<int> dist(C);
        Vec<int> sum(C);
        for (int i = 0; i < C - 1; ++i) {
            sum[i + 1] = sum[i] + side[0][i];
        }
        for (int j = 0; j < C; ++j) {
            dist[j] = std::abs(sum[V1] - sum[j]);
        }
        for (int i = 0; i < R - 1; ++i) {
            for (int j = 0; j < C; ++j) {
                dist[j] += vert[i][j];
            }
            sum[0] = 0;
            for (int j = 0; j < C - 1; ++j) {
                sum[j + 1] = sum[j] + side[i + 1][j];
            }
            int lmin = 1000000000;
            for (int j = 0; j < C; ++j) {
                dist[j] = std::min(dist[j], lmin + sum[j]);
                lmin = std::min(lmin, dist[j] - sum[j]);
            }
            int rmin = 1000000000 + 1000000000;
            for (int j = C - 1; j >= 0; --j) {
                dist[j] = std::min(dist[j], rmin - sum[j]);
                rmin = std::min(rmin, dist[j] + sum[j]);
            }
        }
        return dist[V2];
    }
}

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

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