Submission #1074018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074018		pravcoder	Wombats (IOI13_wombats)	C++17	39 / 100	42 ms	10832 KiB

wombats

#include "wombats.h"
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> v2i;
typedef vector<v2i> v3i;
typedef pair<int, int> pi;
typedef pair<int, pi> p2i;
typedef priority_queue<p2i> djpq; // priority queue for djikstras
typedef vector<bool> vb;
typedef vector<vb> v2b;

#define pb push_back
#define mp make_pair
#define rept(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)

//sub1

v2i h, v;
int r, c;
int totw = 0;
bool sub1 = true;
bool sub2 = true;
bool sub3 = false;
v2i mindists;
v2b processed;
djpq q;
v3i s3dp; //sub 3 dp

void s3update(int r) {
    int s, c;
    if (r != 0) {
        rep(s, 2) {
            rep(c, 2) {
                s3dp[r][c][s] = min(s3dp[r - 1][c][s] + v[r - 1][c], s3dp[r - 1][1 - c][s] + v[r - 1][1 - c] + h[r][0]);
            }
        }
    }
    else {
        rep(s, 2) {
            s3dp[0][1-s][s] = h[0][0];
        }
    }
}

void sub2calc(int start) {
    //cout << "----------------------------Calculating minimum distances for " << start << "----------------------------\n";
    q.push({ 0, {0, start} });
    int d;
    while (!q.empty()) {
        p2i node = q.top();
        d = 0 - node.first;
        //cout << "Processing node (" << node.second.first << ", " << node.second.second << ") with distance " << d << "\n";
        q.pop();
        if (!processed[node.second.first][node.second.second]) {
            //cout << "Adding children\n";
            // process children of node
            if (node.second.second < c - 1) { // right 
                //cout << "Added right node ";
                int newdist = (d + h[node.second.first][node.second.second]);
                q.push({ 0 - newdist, {node.second.first, node.second.second + 1} });
                //cout << "with distance " << newdist << "\n";
            }
            if (node.second.second > 0) { // left
                //cout << "Added left node ";
                int newdist = (d + h[node.second.first][node.second.second - 1]);
                q.push({ 0 - newdist, {node.second.first, node.second.second - 1} });
                //cout << "with distance " << newdist << "\n";
            }
            if (node.second.first < r - 1) { // bottom
                //cout << "Added bottom node ";
                int newdist = (d + v[node.second.first][node.second.second]);
                q.push({ 0 - newdist, {node.second.first + 1, node.second.second} });
                //cout << "with distance " << newdist << "\n";
            }
            else {
                mindists[start][node.second.second] = d;
                //cout << "Minimum distance for " << node.second.second << " is " << d << "\n";
            }
            processed[node.second.first][node.second.second] = true;
        }
    }
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    vi tmp;
    r = R, c = C;
    if (C != 1) sub1 = false;
    if (max(R, C) > 20) {
        sub2 = false;
    }
    if (C == 2) {
        sub3 = true;
        sub2 = false;
    }
    if (sub2) {
        mindists.resize(C, vi(C, 1000000000));
    }
    rep(i, R) {
        tmp.clear();
        rep(j, C - 1) {
            tmp.pb(H[i][j]);
        }
        h.pb(tmp);
    }
    rep(i, R-1) {
        tmp.clear();
        rep(j, C) {
            tmp.pb(V[i][j]);
            if (sub1) totw += V[i][j];
        }
        v.pb(tmp);
    }
    if (sub2) {
        rep(i, c) {
            processed.clear();
            processed.resize(R, vb(C, false));
            sub2calc(i);
        }
    }
    if (sub3) {
        s3dp.resize(r, v2i(c, vi(2)));
        rep(i, r) {
            s3update(i);
            //cout << "Initial dp update " << i << "\n";
        }
    }
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    if (sub3) {
        rept(i, P, r) {
            s3update(i);
            //cout << "dp update " << i << "\n";
        }
    }
}

void changeV(int P, int Q, int W) {
    totw += W - v[P][Q];
    v[P][Q] = W;
    if (sub3) {
        rept(i, P+1, r) {
            s3update(i);
            //cout << "dp update " << i << "\n";
        }
    }
}

int escape(int V1, int V2) {
    if (sub1) {
        return totw;
    }
    if (sub2) {
        
        return mindists[V1][V2];
    }
    if (sub3) {
        return s3dp[r - 1][V2][V1];
    }
}

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 s3update(int)':
wombats.cpp:40:9: warning: unused variable 's' [-Wunused-variable]
   40 |     int s, c;
      |         ^
wombats.cpp:40:12: warning: unused variable 'c' [-Wunused-variable]
   40 |     int s, c;
      |            ^
wombats.cpp: In function 'int escape(int, int)':
wombats.cpp:171:1: warning: control reaches end of non-void function [-Wreturn-type]
  171 | }
      | ^

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