oj.uz

Submission #155849

# Submission time Handle Problem Language Result Execution time Memory
155849 2019-10-01T05:36:24 Z TAISA_ Wombats (IOI13_wombats) C++14
0 / 100
 282 ms 8568 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];
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    h = R, w = C;
    if (w == 1) {
        type = 1;
    } 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 += 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:107:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4600 KB Output is correct
2 Incorrect 6 ms 4600 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Incorrect 2 ms 632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 1596 KB Output is correct
2 Correct 275 ms 1768 KB Output is correct
3 Correct 188 ms 1656 KB Output is correct
4 Correct 183 ms 1528 KB Output is correct
5 Correct 188 ms 1528 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Incorrect 2 ms 632 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 1728 KB Output is correct
2 Correct 282 ms 1816 KB Output is correct
3 Correct 183 ms 1528 KB Output is correct
4 Correct 182 ms 1656 KB Output is correct
5 Correct 182 ms 1528 KB Output is correct
6 Incorrect 11 ms 8440 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 1532 KB Output is correct
2 Correct 270 ms 1836 KB Output is correct
3 Correct 183 ms 1528 KB Output is correct
4 Correct 187 ms 1528 KB Output is correct
5 Correct 188 ms 1592 KB Output is correct
6 Incorrect 11 ms 8440 KB Output isn't correct
7 Halted 0 ms 0 KB -