oj.uz

Submission #250992

# Submission time Handle Problem Language Result Execution time Memory
250992 2020-07-19T19:16:53 Z A02 Wombats (IOI13_wombats) C++14
16 / 100
 20000 ms 9932 KB 
#include "wombats.h"
#include <vector>
#include <set>
#include <algorithm>
#include <utility>
#include <queue>
#include <iostream>

using namespace std;

int R;
int C;
vector<vector<long long> > Hwombats;
vector<vector<long long> > Vwombats;
vector<vector<long long> > escapeCostV2V1;

void fill_escape_costs(){

    for (int v1 = 0; v1 < C; v1++){

        priority_queue<pair<long long, pair<int, int> > > to_visit;

        vector<vector<long long> > costs (R, vector<long long> (C,(R + C) * 2000));

        to_visit.push(make_pair(0, make_pair(0, v1)));

        while (!to_visit.empty()){

            pair<long long, pair<int, int> > current = to_visit.top();
            to_visit.pop();
            long long d = -current.first;
            int r = current.second.first;
            int c = current.second.second;
            if (costs[r][c] == (R + C) * 2000){

                costs[r][c] = d;

                if (c != 0){
                    int nr = r;
                    int nc = c - 1;
                    long long nd = d + Hwombats[r][c - 1];
                    to_visit.push(make_pair(-nd, make_pair(nr, nc)));
                }
                if (c != C - 1){
                    int nr = r;
                    int nc = c + 1;
                    long long nd = d + Hwombats[r][c];
                    to_visit.push(make_pair(-nd, make_pair(nr, nc)));
                }
                if (r != R - 1){
                    int nr = r + 1;
                    int nc = c;
                    long long nd = d + Vwombats[r][c];
                    to_visit.push(make_pair(-nd, make_pair(nr, nc)));
                }
            }

        }

        for (int v2 = 0; v2 < C; v2++){
            escapeCostV2V1[v2][v1] = costs[R - 1][v2];
            //cout << v1 << ' ' << v2 << ' ' << costs[R - 1][v2] << endl;
        }

    }

}

void init(int r, int c, int H[5000][200], int V[5000][200]) {
    R = r;
    C = c;
    Hwombats = vector<vector<long long> > (R, vector<long long> (C - 1, 0));
    Vwombats = vector<vector<long long> > (R - 1, vector<long long> (C, 0));

    for (int i = 0; i < R; i++){
        for (int j = 0; j < C - 1; j++){
            Hwombats[i][j] = H[i][j];
        }
    }

    for (int i = 0; i < R - 1; i++){
        for (int j = 0; j < C; j++){
            Vwombats[i][j] = V[i][j];
        }
    }

    escapeCostV2V1 = vector<vector<long long> > (C, vector<long long> (C, 0));
    //fill_escape_costs();
}

void changeH(int P, int Q, int W) {
    Hwombats[P][Q] = W;
    //fill_escape_costs();
}

void changeV(int P, int Q, int W) {
    Vwombats[P][Q] = W;
    //fill_escape_costs();
}

int escape(int V1, int V2) {
    int v1 = V1;
        priority_queue<pair<long long, pair<int, int> > > to_visit;

        vector<vector<long long> > costs (R, vector<long long> (C,(R + C) * 2000));

        to_visit.push(make_pair(0, make_pair(0, v1)));

        while (!to_visit.empty()){

            pair<long long, pair<int, int> > current = to_visit.top();
            to_visit.pop();
            long long d = -current.first;
            int r = current.second.first;
            int c = current.second.second;
            if (costs[r][c] == (R + C) * 2000){

                costs[r][c] = d;

                if (c != 0){
                    int nr = r;
                    int nc = c - 1;
                    long long nd = d + Hwombats[r][c - 1];
                    to_visit.push(make_pair(-nd, make_pair(nr, nc)));
                }
                if (c != C - 1){
                    int nr = r;
                    int nc = c + 1;
                    long long nd = d + Hwombats[r][c];
                    to_visit.push(make_pair(-nd, make_pair(nr, nc)));
                }
                if (r != R - 1){
                    int nr = r + 1;
                    int nc = c;
                    long long nd = d + Vwombats[r][c];
                    to_visit.push(make_pair(-nd, make_pair(nr, nc)));
                }
            }

        }

    return costs[R - 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;
      ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 5428 KB Output is correct
2 Correct 189 ms 4944 KB Output is correct
3 Execution timed out 20062 ms 5412 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 60 ms 448 KB Output is correct
5 Correct 33 ms 384 KB Output is correct
6 Correct 42 ms 384 KB Output is correct
7 Correct 37 ms 384 KB Output is correct
8 Correct 35 ms 428 KB Output is correct
9 Correct 38 ms 384 KB Output is correct
10 Correct 36 ms 384 KB Output is correct
11 Execution timed out 20064 ms 1628 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 888 KB Output is correct
2 Correct 461 ms 1408 KB Output is correct
3 Correct 332 ms 976 KB Output is correct
4 Correct 333 ms 976 KB Output is correct
5 Correct 338 ms 1016 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 337 ms 1096 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1254 ms 9272 KB Output is correct
2 Correct 1959 ms 9028 KB Output is correct
3 Correct 1262 ms 9372 KB Output is correct
4 Execution timed out 20094 ms 9388 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 884 KB Output is correct
2 Correct 483 ms 1456 KB Output is correct
3 Correct 333 ms 1016 KB Output is correct
4 Correct 334 ms 1016 KB Output is correct
5 Correct 351 ms 964 KB Output is correct
6 Correct 1290 ms 9088 KB Output is correct
7 Correct 2041 ms 9332 KB Output is correct
8 Correct 1333 ms 9152 KB Output is correct
9 Execution timed out 20020 ms 9808 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 888 KB Output is correct
2 Correct 464 ms 1404 KB Output is correct
3 Correct 334 ms 896 KB Output is correct
4 Correct 360 ms 1016 KB Output is correct
5 Correct 345 ms 896 KB Output is correct
6 Correct 1310 ms 9264 KB Output is correct
7 Correct 2073 ms 9380 KB Output is correct
8 Correct 1266 ms 9168 KB Output is correct
9 Execution timed out 20045 ms 9932 KB Time limit exceeded
10 Halted 0 ms 0 KB -