oj.uz

Submission #1073984

# Submission time Handle Problem Language Result Execution time Memory
1073984 2024-08-25T05:57:29 Z pravcoder Wombats (IOI13_wombats) C++17
21 / 100
 40 ms 17752 KB 
#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 pair<int, int> pi;
typedef pair<int, pi> p2i;
typedef priority_queue<p2i> djpq;
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;
v2i mindists;
v2b processed;
djpq q;

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;
    }
    else {
        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);
        }
    }
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
}

void changeV(int P, int Q, int W) {
    totw += W - v[P][Q];
    v[P][Q] = W;
}

int escape(int V1, int V2) {
    if (sub1) {
        return totw;
    }
    else if (sub2) {
        return mindists[V1][V2];
    }
}

Compilation message

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 'int escape(int, int)':
wombats.cpp:125:1: warning: control reaches end of non-void function [-Wreturn-type]
  125 | }
      | ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4636 KB Output is correct
2 Correct 2 ms 4636 KB Output is correct
3 Correct 39 ms 7492 KB Output is correct
4 Correct 3 ms 4636 KB Output is correct
5 Correct 2 ms 4636 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 444 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 40 ms 2700 KB Output is correct
12 Correct 2 ms 348 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 17752 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 996 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -