oj.uz

Submission #155851

# Submission time Handle Problem Language Result Execution time Memory
155851 2019-10-01T05:59:27 Z TAISA_ Wombats (IOI13_wombats) C++14
55 / 100
 10016 ms 26040 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8440 KB Output is correct
2 Correct 11 ms 8440 KB Output is correct
3 Correct 79 ms 9976 KB Output is correct
4 Correct 9 ms 8440 KB Output is correct
5 Correct 9 ms 8440 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 504 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 30 ms 760 KB Output is correct
5 Correct 13 ms 760 KB Output is correct
6 Correct 15 ms 764 KB Output is correct
7 Correct 31 ms 760 KB Output is correct
8 Correct 19 ms 760 KB Output is correct
9 Correct 22 ms 760 KB Output is correct
10 Correct 21 ms 760 KB Output is correct
11 Correct 10010 ms 1920 KB Output is correct
12 Correct 31 ms 760 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 1680 KB Output is correct
2 Correct 268 ms 1824 KB Output is correct
3 Correct 184 ms 1784 KB Output is correct
4 Correct 187 ms 1700 KB Output is correct
5 Correct 194 ms 1716 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 257 ms 1784 KB Output is correct
10 Correct 2 ms 632 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 16420 KB Output is correct
2 Correct 62 ms 16376 KB Output is correct
3 Correct 62 ms 16408 KB Output is correct
4 Correct 99 ms 17752 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 1684 KB Output is correct
2 Correct 271 ms 2000 KB Output is correct
3 Correct 190 ms 1784 KB Output is correct
4 Correct 186 ms 1784 KB Output is correct
5 Correct 188 ms 1784 KB Output is correct
6 Correct 62 ms 16380 KB Output is correct
7 Correct 59 ms 16380 KB Output is correct
8 Correct 89 ms 16376 KB Output is correct
9 Correct 99 ms 17784 KB Output is correct
10 Correct 9 ms 8440 KB Output is correct
11 Correct 10 ms 8440 KB Output is correct
12 Correct 86 ms 11336 KB Output is correct
13 Correct 11 ms 8440 KB Output is correct
14 Correct 11 ms 8440 KB Output is correct
15 Correct 2 ms 632 KB Output is correct
16 Correct 3 ms 632 KB Output is correct
17 Correct 3 ms 632 KB Output is correct
18 Correct 32 ms 760 KB Output is correct
19 Correct 13 ms 760 KB Output is correct
20 Correct 15 ms 760 KB Output is correct
21 Correct 31 ms 796 KB Output is correct
22 Correct 20 ms 888 KB Output is correct
23 Correct 23 ms 760 KB Output is correct
24 Correct 20 ms 760 KB Output is correct
25 Correct 10016 ms 3448 KB Output is correct
26 Correct 30 ms 888 KB Output is correct
27 Correct 255 ms 1812 KB Output is correct
28 Incorrect 133 ms 20216 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 1784 KB Output is correct
2 Correct 284 ms 1988 KB Output is correct
3 Correct 190 ms 1656 KB Output is correct
4 Correct 183 ms 1656 KB Output is correct
5 Correct 189 ms 1784 KB Output is correct
6 Correct 71 ms 16376 KB Output is correct
7 Correct 59 ms 16504 KB Output is correct
8 Correct 62 ms 16452 KB Output is correct
9 Correct 103 ms 17784 KB Output is correct
10 Correct 11 ms 8444 KB Output is correct
11 Correct 12 ms 8440 KB Output is correct
12 Correct 81 ms 11256 KB Output is correct
13 Correct 10 ms 8568 KB Output is correct
14 Correct 9 ms 8448 KB Output is correct
15 Incorrect 219 ms 26040 KB Output isn't correct
16 Halted 0 ms 0 KB -