Submission #941078

#	Time	Username	Problem	Language	Result	Execution time	Memory
941078		vjudge1	Wombats (IOI13_wombats)	C++17	76 / 100	20056 ms	183868 KiB

wombats

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <x86intrin.h>

#include <bits/stdc++.h>
using namespace std;

#include "wombats.h"

#define f first
#define s second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back

int n, m;
vector<vector<int>> hor, vert;

struct segTree
{
    struct Node
    {
        vector<vector<int>> dist;
    };
    vector<Node> tree;
    int sz = 0;

    void init(int n)
    {
        sz = 1;
        while (sz < n)
            sz *= 2;
        tree.resize(2 * sz);
    }

    void merge(Node &res, Node &a, Node &b)
    {
        if (b.dist.size() == 0)
        {
            res = a;
            return;
        }

        int c = a.dist.size();

        if (res.dist.size() == 0)
            res.dist.resize(c, vector<int>(c));

        vector<vector<int>> opt(m, vector<int>(m));

        int cntO = 0;

        for (int val = -(c + 1); val < c; ++val)
            for (int i = 0; i < c; ++i)
            {
                int j = i - val;

                if (j >= 0 and j < c)
                {
                    res.dist[i][j] = 1e9 + 500;
                    int L = i ? opt[i - 1][j] : 0;
                    int R = j + 1 < c ? opt[i][j + 1] : m - 1;
                    for (int p = L; p <= R; ++p)
                        if (res.dist[i][j] > a.dist[i][p] + b.dist[p][j])
                        {
                            cntO++;
                            if (cntO > 1e6)
                                exit(0);
                            res.dist[i][j] = a.dist[i][p] + b.dist[p][j];
                            opt[i][j] = p;
                        }
                }
            }
    }

    void build(vector<vector<vector<int>>> &bf, int v, int lv, int rv)
    {
        if (rv - lv == 1)
        {
            if (lv < bf.size())
                tree[v].dist = bf[lv];
            return;
        }
        int m = (lv + rv) >> 1;
        build(bf, v * 2 + 1, lv, m);
        build(bf, v * 2 + 2, m, rv);
        merge(tree[v], tree[v * 2 + 1], tree[v * 2 + 2]);
    }

    void build(vector<vector<vector<int>>> &bf)
    {
        init(bf.size());
        build(bf, 0, 0, sz);
    }

    void set(int pos, vector<vector<int>> &dists, int v, int lv, int rv)
    {
        if (rv - lv == 1)
        {
            tree[v].dist = dists;
            return;
        }
        int m = (lv + rv) >> 1;
        if (pos < m)
            set(pos, dists, v * 2 + 1, lv, m);
        else
            set(pos, dists, v * 2 + 2, m, rv);
        merge(tree[v], tree[v * 2 + 1], tree[v * 2 + 2]);
        // cout << lv << " " << rv << ":\n";
        // for (int i = 0; i < tree[v].dist.size(); ++i)
        //     for (int j = 0; j < tree[v].dist.size(); ++j)
        //         cout << i << " " << j << ": " << tree[v].dist[i][j] << "\n";

        // cout << "\n";
    }

    void set(int pos, vector<vector<int>> &dists)
    {
        set(pos, dists, 0, 0, sz);
    }
};

segTree tree;

vector<vector<int>> calc(int x)
{
    vector<vector<int>> dists;

    dists.resize(m, vector<int>(m, 1e9 + 10));

    int l = x;
    int r = min(x + 15, n - 1);

    vector<int> newD(m);
    for (int st = 0; st < m; ++st)
    {
        auto &d = dists[st];
        d[st] = 0;
        for (int i = 1; i < m; ++i)
            d[i] = min(d[i], d[i - 1] + hor[l][i - 1]);
        for (int i = m - 2; i >= 0; --i)
            d[i] = min(d[i], d[i + 1] + hor[l][i]);

        for (int x = l; x < r; ++x)
        {
            for (int i = 0; i < m; ++i)
                newD[i] = d[i] + vert[x][i];

            for (int i = 1; i < m; ++i)
                newD[i] = min(newD[i], newD[i - 1] + hor[x + 1][i - 1]);
            for (int i = m - 2; i >= 0; --i)
                newD[i] = min(newD[i], newD[i + 1] + hor[x + 1][i]);

            d = newD;
        }
    }

    return dists;
}

void init(int R, int C, int H[5000][200], int V[5000][200])
{
    n = R;
    m = C;

    hor.resize(n + 1, vector<int>(m + 1));
    vert.resize(n + 1, vector<int>(m + 1));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
        {
            if (j + 1 < m)
                hor[i][j] = H[i][j];
            if (i + 1 < n)
                vert[i][j] = V[i][j];
        }

    vector<vector<vector<int>>> bf;
    for (int i = 0; i + 1 < n; i += 15)
    {
        vector<vector<int>> cur = calc(i);
        bf.pb(cur);
    }
    tree.build(bf);
}

void changeH(int P, int Q, int W)
{
    /* ... */
    hor[P][Q] = W;
    if (P)
    {
        vector<vector<int>> cur = calc(((P - 1) / 15) * 15);
        tree.set((P - 1) / 15, cur);
    }
    if (P != n - 1)
    {
        vector<vector<int>> cur = calc((P / 15) * 15);
        tree.set(P / 15, cur);
    }
}

void changeV(int P, int Q, int W)
{
    /* ... */
    vert[P][Q] = W;
    if (P)
    {
        vector<vector<int>> cur = calc(((P - 1) / 15) * 15);
        tree.set((P - 1) / 15, cur);
    }
    if (P != n - 1)
    {
        vector<vector<int>> cur = calc((P / 15) * 15);
        tree.set(P / 15, cur);
    }
}

int escape(int V1, int V2)
{
    return tree.tree[0].dist[V1][V2];
}

// // /////////////////////////////

// #include <stdio.h>
// #include <stdlib.h>
// #include <assert.h>
// #include <vector>
// #include "wombats.h"

// static int H[5000][200];
// static int V[5000][200];

// int main()
// {
//     int R, C, E, P, Q, W, V1, V2, event, i, j;

//     assert(scanf("%d%d", &R, &C) == 2);
//     for (i = 0; i < R; ++i)
//         for (j = 0; j < C - 1; ++j)
//             assert(scanf("%d", &H[i][j]) == 1);
//     for (i = 0; i < R - 1; ++i)
//         for (j = 0; j < C; ++j)
//             assert(scanf("%d", &V[i][j]) == 1);

//     init(R, C, H, V);

//     std::vector<int> answers;

//     assert(scanf("%d", &E) == 1);
//     for (i = 0; i < E; i++)
//     {
//         assert(scanf("%d", &event) == 1);
//         if (event == 1)
//         {
//             assert(scanf("%d%d%d", &P, &Q, &W) == 3);
//             changeH(P, Q, W);
//         }
//         else if (event == 2)
//         {
//             assert(scanf("%d%d%d", &P, &Q, &W) == 3);
//             changeV(P, Q, W);
//         }
//         else if (event == 3)
//         {
//             assert(scanf("%d%d", &V1, &V2) == 2);
//             answers.push_back(escape(V1, V2));
//         }
//     }
//     for (int ans : answers)
//     {
//         printf("%d\n", ans);
//     }
//     return 0;
// }

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 member function 'void segTree::build(std::vector<std::vector<std::vector<int> > >&, int, int, int)':
wombats.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             if (lv < bf.size())
      |                 ~~~^~~~~~~~~~~

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