oj.uz

Submission #1067869

# Submission time Handle Problem Language Result Execution time Memory
1067869 2024-08-21T04:55:04 Z kunzaZa183 Wombats (IOI13_wombats) C++17
37 / 100
 20000 ms 20476 KB 
#include "wombats.h"
#include <bits/stdc++.h>
#include <utility>
using namespace std;


struct qry{
  pair<int,int> pos;
  int w;
  bool operator<(qry x) const{
    return w > x.w;
  }
};

int hori[5000][200],verti[5000][200];
int dp[5000][200],r,c;

const int big = 1e9+7;
void dij(int a,int b){
  priority_queue<qry> pq;
  for(int i = 0; i < r; i++)
    for(int j = 0; j< c;j++)
      dp[i][j] = big;

    qry tmp;
    tmp.pos = {a,b};
    tmp.w = 0;
    pq.push(tmp);

  while(!pq.empty()) {
    qry x = pq.top();
    pq.pop();
    if(dp[x.pos.first][x.pos.second] == big) {
      dp[x.pos.first][x.pos.second] = x.w;
      qry sth;
      if(x.pos.second!=0) {
        sth.pos = {x.pos.first,x.pos.second - 1};
        sth.w = hori[sth.pos.first][sth.pos.second] + x.w;
        pq.push(sth);
      }
      if(x.pos.second != c - 1) {
        sth.pos = {x.pos.first, x.pos.second + 1};
        sth.w = hori[x.pos.first][x.pos.second] + x.w;
        pq.push(sth);
      }
      if(x.pos.first != 0) {
        sth.pos = {x.pos.first - 1,x.pos.second};
        sth.w = verti[sth.pos.first][sth.pos.second] + x.w;
        pq.push(sth);
      } 
    }
  }
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
  r = R, c= C;
  for(int i =0; i < R;i++)
    for(int j = 0; j < C;j++)
      hori[i][j] = H[i][j], verti[i][j] = V[i][j];
}



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

void changeV(int P, int Q, int W) {
  verti[P][Q] = W;
}

int escape(int V1, int V2) {
  dij(r-1,V2);
  return dp[0][V1];
}

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 'void dij(int, int)':
wombats.cpp:21:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   21 |   for(int i = 0; i < r; i++)
      |   ^~~
wombats.cpp:25:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   25 |     qry tmp;
      |     ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 17756 KB Output is correct
2 Correct 34 ms 17752 KB Output is correct
3 Correct 12810 ms 19448 KB Output is correct
4 Correct 35 ms 17752 KB Output is correct
5 Correct 35 ms 17940 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 18 ms 8676 KB Output is correct
5 Correct 10 ms 8540 KB Output is correct
6 Correct 10 ms 8668 KB Output is correct
7 Correct 13 ms 8540 KB Output is correct
8 Correct 19 ms 8676 KB Output is correct
9 Correct 23 ms 8540 KB Output is correct
10 Correct 21 ms 8540 KB Output is correct
11 Correct 11891 ms 9556 KB Output is correct
12 Correct 20 ms 8540 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 8536 KB Output is correct
2 Correct 231 ms 9040 KB Output is correct
3 Correct 201 ms 8540 KB Output is correct
4 Correct 197 ms 8540 KB Output is correct
5 Correct 212 ms 8784 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 183 ms 8772 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 19804 KB Output is correct
2 Correct 941 ms 19992 KB Output is correct
3 Correct 507 ms 19804 KB Output is correct
4 Execution timed out 20053 ms 20244 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 8736 KB Output is correct
2 Correct 230 ms 9024 KB Output is correct
3 Correct 198 ms 8536 KB Output is correct
4 Correct 204 ms 8536 KB Output is correct
5 Correct 220 ms 8540 KB Output is correct
6 Correct 498 ms 19804 KB Output is correct
7 Correct 967 ms 20052 KB Output is correct
8 Correct 517 ms 19804 KB Output is correct
9 Execution timed out 20051 ms 20288 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 8536 KB Output is correct
2 Correct 230 ms 9024 KB Output is correct
3 Correct 199 ms 8540 KB Output is correct
4 Correct 199 ms 8536 KB Output is correct
5 Correct 195 ms 8728 KB Output is correct
6 Correct 501 ms 19804 KB Output is correct
7 Correct 994 ms 19800 KB Output is correct
8 Correct 488 ms 19800 KB Output is correct
9 Execution timed out 20054 ms 20476 KB Time limit exceeded
10 Halted 0 ms 0 KB -