Submission #155851

#	Time	Username	Problem	Language	Result	Execution time	Memory
155851		TAISA_	Wombats (IOI13_wombats)	C++14	55 / 100	10016 ms	26040 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = (1 << 30) - 1;
const ll LINF = (1LL << 60) - 1LL;
int type, h, w, sum1;
struct edge {
    int y, x, cst;
};
vector<edge> G[110][110];
int d[110][110], dp0[5001][2], dp1[5001][2];
int v[5000][200], hh[5000][200];
void recalc() {
    for (int i = 0; i <= h; i++) {
        dp0[i][0] = INF;
        dp0[i][1] = INF;
        dp1[i][0] = INF;
        dp1[i][1] = INF;
    }
    dp0[0][0] = 0;
    dp0[0][1] = hh[0][0];
    dp1[0][1] = 0;
    dp1[0][0] = hh[0][0];
    for (int i = 1; i < h; i++) {
        dp0[i][0] = min(dp0[i - 1][0] + v[i - 1][0],
                        dp0[i - 1][1] + v[i - 1][1] + hh[i][0]);
        dp0[i][1] = min(dp0[i - 1][1] + v[i - 1][1],
                        dp0[i - 1][0] + v[i - 1][0] + hh[i][0]);
        dp1[i][0] = min(dp1[i - 1][0] + v[i - 1][0],
                        dp1[i - 1][1] + v[i - 1][1] + hh[i][0]);
        dp1[i][1] = min(dp1[i - 1][1] + v[i - 1][1],
                        dp1[i - 1][0] + v[i - 1][0] + hh[i][0]);
    }
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    h = R, w = C;
    sum1 = 0;
    for (int i = 0; i < h - 1; i++) {
        for (int j = 0; j < w; j++) {
            v[i][j] = V[i][j];
        }
    }
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w - 1; j++) {
            hh[i][j] = H[i][j];
        }
    }
    if (w == 1) {
        type = 1;
        for (int i = 0; i < h - 1; i++) {
            sum1 += V[i][0];
        }
    } else if (h <= 20 && w <= 20) {
        type = 2;
    } else if (h <= 100 && w <= 100) {
        type = 3;
    } else if (w == 2) {
        type = 4;
    }
    if (type == 2 || type == 3) {
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w - 1; j++) {
                G[i][j].push_back(edge{i, j + 1, H[i][j]});
                G[i][j + 1].push_back(edge{i, j, H[i][j]});
            }
        }
        for (int i = 0; i < h - 1; i++) {
            for (int j = 0; j < w; j++) {
                G[i][j].push_back(edge{i + 1, j, V[i][j]});
            }
        }
    } else if (type == 4) {
        recalc();
    }
}

void changeH(int P, int Q, int W) {
    if (type == 2 || type == 3) {
        vector<edge> to;
        for (auto &e : G[P][Q]) {
            if (e.y == P && e.x == Q + 1) {
                continue;
            }
            to.push_back(e);
        }
        to.push_back(edge{P, Q + 1, W});
        G[P][Q] = to;
        to.clear();
        for (auto &e : G[P][Q + 1]) {
            if (e.y == P && e.x == Q) {
                continue;
            }
            to.push_back(e);
        }
        to.push_back(edge{P, Q, W});
        G[P][Q + 1] = to;
    } else if (type == 4) {
        hh[P][Q] = W;
        recalc();
    }
}

void changeV(int P, int Q, int W) {
    if (type == 1) {
        sum1 -= v[P][Q];
        sum1 += W;
        v[P][Q] = W;
    } else if (type == 2 || type == 3) {
        vector<edge> to;
        for (auto &e : G[P][Q]) {
            if (e.y == P + 1 && e.x == Q) {
                continue;
            }
            to.push_back(e);
        }
        to.push_back(edge{P + 1, Q, W});
        G[P][Q] = to;
    } else if (type == 4) {
        v[P][Q] = W;
        recalc();
    }
}

int escape(int V1, int V2) {
    if (type == 1) {
        return sum1;
    } else if (type == 2 || type == 3) {
        priority_queue<pair<int, P>, vector<pair<int, P>>,
                       greater<pair<int, P>>>
            q;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                d[i][j] = INF;
            }
        }
        d[0][V1] = 0;
        q.push(make_pair(0, P(0, V1)));
        while (!q.empty()) {
            int ds = q.top().first, y = q.top().second.first,
                x = q.top().second.second;
            q.pop();
            if (ds > d[y][x]) {
                continue;
            }
            for (auto &e : G[y][x]) {
                if (d[e.y][e.x] > d[y][x] + e.cst) {
                    d[e.y][e.x] = d[y][x] + e.cst;
                    q.push(make_pair(d[e.y][e.x], P(e.y, e.x)));
                }
            }
        }
        return d[h - 1][V2];
    } else if (type == 4) {
        if (V1 == 0) {
            return dp0[h - 1][V2];
        } else {
            return dp1[h - 1][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]
  int res;
      ^~~
wombats.cpp: In function 'int escape(int, int)':
wombats.cpp:162:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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