oj.uz

Submission #155850

# Submission time Handle Problem Language Result Execution time Memory
155850 2019-10-01T05:46:59 Z TAISA_ Wombats (IOI13_wombats) C++14
37 / 100
 10044 ms 12280 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];
int v[5000][200];
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];
        }
    }
    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;
    }
    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]});
            }
        }
    }
}

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;
    }
}

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;
    }
}

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];
    }
}

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:119: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 9 ms 8440 KB Output is correct
2 Correct 9 ms 8440 KB Output is correct
3 Correct 81 ms 11360 KB Output is correct
4 Correct 9 ms 8440 KB Output is correct
5 Correct 10 ms 8568 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 760 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 3 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 760 KB Output is correct
7 Correct 32 ms 760 KB Output is correct
8 Correct 19 ms 760 KB Output is correct
9 Correct 22 ms 764 KB Output is correct
10 Correct 20 ms 760 KB Output is correct
11 Correct 10044 ms 3332 KB Output is correct
12 Correct 30 ms 764 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 1528 KB Output is correct
2 Correct 265 ms 1768 KB Output is correct
3 Correct 182 ms 1628 KB Output is correct
4 Correct 184 ms 1528 KB Output is correct
5 Correct 182 ms 1604 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 632 KB Output is correct
9 Correct 257 ms 1732 KB Output is correct
10 Correct 2 ms 632 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 12280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 1528 KB Output is correct
2 Correct 270 ms 1860 KB Output is correct
3 Correct 185 ms 1620 KB Output is correct
4 Correct 181 ms 1612 KB Output is correct
5 Correct 200 ms 1600 KB Output is correct
6 Incorrect 14 ms 12280 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 1628 KB Output is correct
2 Correct 301 ms 1852 KB Output is correct
3 Correct 194 ms 1616 KB Output is correct
4 Correct 195 ms 1528 KB Output is correct
5 Correct 184 ms 1656 KB Output is correct
6 Incorrect 14 ms 12280 KB Output isn't correct
7 Halted 0 ms 0 KB -