Submission #1076200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076200		shmax	Wombats (IOI13_wombats)	C++17	55 / 100	20056 ms	262144 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

template<typename T>
using vec = vector<T>;
vec<vec<pair<int, int>>> g;
vec<vec<int>> dists;

void dijkstra(int start, vec<int> &dist) {
    dist.clear();
    dist.resize(g.size());
    fill(dist.begin(), dist.end(), 1e9);
    dist[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, start});
    while (!pq.empty()) {
        auto [d, v] = pq.top();
        pq.pop();
        if (d > dist[v]) continue;
        for (auto [u, w]: g[v]) {
            if (dist[u] > dist[v] + w) {
                dist[u] = dist[v] + w;
                pq.push({dist[u], u});
            }
        }
    }
}

int r, c;

void calc() {
    for (int i = 0; i < c; i++) {
        dijkstra(i, dists[i]);
    }
}


void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r = R;
    c = C;
    g.resize(R * C);
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (i != R - 1) {
                g[i * C + j].emplace_back(i * C + j + C, V[i][j]);
            }
            if (j != 0) {
                g[i * C + j].emplace_back(i * C + j - 1, H[i][j - 1]);
            }
            if (j != C - 1) {
                g[i * C + j].emplace_back(i * C + j + 1, H[i][j]);
            }
        }
    }
    dists.resize(C);
    calc();
}

void changeH(int x, int y, int val) {
    for (int i = 0; i < g[x * c + y].size(); i++) {
        if (g[x * c + y][i].first == x * c + y + 1) {
            g[x * c + y][i].second = val;
            break;
        }
    }
    for (int i = 0; i < g[x * c + y + 1].size(); i++) {
        if (g[x * c + y + 1][i].first == x * c + y) {
            g[x * c + y + 1][i].second = val;
            break;
        }
    }
    if (c <= 2)
        calc();
}

void changeV(int x, int y, int val) {
    for (int i = 0; i < g[x * c + y].size(); i++) {
        if (g[x * c + y][i].first == x * c + y + c) {
            g[x * c + y][i].second = val;
            break;
        }
    }

    if (c <= 2)
        calc();
}

int escape(int y1, int y2) {
    if (c > 2)
        dijkstra(y1, dists[y1]);
    return dists[y1][r * c - c + y2];
}

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 function 'void changeH(int, int, int)':
wombats.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int i = 0; i < g[x * c + y].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~
wombats.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int i = 0; i < g[x * c + y + 1].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i = 0; i < g[x * c + y].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~

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