oj.uz

Submission #1068052

# Submission time Handle Problem Language Result Execution time Memory
1068052 2024-08-21T06:57:47 Z kunzaZa183 Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 27916 KB 
#pragma GCC optimizeation ("O3")

#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;
int ans[200][200];

bitset<200> alrdid;

const int big = 1e9+7;
void dij(int a,int b,int in){
  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);
      } 
    }
  }

  for(int i = 0; i < c;i++)
    ans[in][i] = dp[0][i];
}

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];
  alrdid.reset();
}



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

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

int escape(int V1, int V2) {
  if(!alrdid[V2])
    dij(r-1,V2,V2);
  alrdid[V2] = 1;
  return ans[V2][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:1: warning: ignoring '#pragma GCC optimizeation' [-Wunknown-pragmas]
    1 | #pragma GCC optimizeation ("O3")
      | 
wombats.cpp: In function 'void dij(int, int, int)':
wombats.cpp:26:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   26 |   for(int i = 0; i < r; i++)
      |   ^~~
wombats.cpp:30:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   30 |     qry tmp;
      |     ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 15960 KB Output is correct
2 Correct 45 ms 16116 KB Output is correct
3 Correct 78 ms 18296 KB Output is correct
4 Correct 40 ms 15964 KB Output is correct
5 Correct 40 ms 15964 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 344 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 580 KB Output is correct
11 Correct 44 ms 2668 KB Output is correct
12 Correct 2 ms 344 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 1004 KB Output is correct
2 Correct 254 ms 1284 KB Output is correct
3 Correct 198 ms 860 KB Output is correct
4 Correct 195 ms 992 KB Output is correct
5 Correct 198 ms 1264 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 348 KB Output is correct
9 Correct 92 ms 1000 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 20060 KB Output is correct
2 Correct 974 ms 20060 KB Output is correct
3 Correct 523 ms 20056 KB Output is correct
4 Correct 571 ms 21104 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 856 KB Output is correct
2 Correct 231 ms 1288 KB Output is correct
3 Correct 213 ms 1112 KB Output is correct
4 Correct 223 ms 1012 KB Output is correct
5 Correct 200 ms 856 KB Output is correct
6 Correct 555 ms 20060 KB Output is correct
7 Correct 1027 ms 20060 KB Output is correct
8 Correct 562 ms 20060 KB Output is correct
9 Correct 606 ms 21100 KB Output is correct
10 Correct 39 ms 15964 KB Output is correct
11 Correct 52 ms 15944 KB Output is correct
12 Correct 85 ms 18256 KB Output is correct
13 Correct 43 ms 15964 KB Output is correct
14 Correct 46 ms 16112 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 448 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 2 ms 348 KB Output is correct
23 Correct 2 ms 344 KB Output is correct
24 Correct 2 ms 348 KB Output is correct
25 Correct 75 ms 2444 KB Output is correct
26 Correct 2 ms 344 KB Output is correct
27 Correct 109 ms 1000 KB Output is correct
28 Execution timed out 20046 ms 22112 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 1008 KB Output is correct
2 Correct 243 ms 1296 KB Output is correct
3 Correct 213 ms 1024 KB Output is correct
4 Correct 214 ms 1004 KB Output is correct
5 Correct 205 ms 964 KB Output is correct
6 Correct 616 ms 20060 KB Output is correct
7 Correct 1008 ms 20060 KB Output is correct
8 Correct 570 ms 20056 KB Output is correct
9 Correct 586 ms 21336 KB Output is correct
10 Correct 44 ms 16100 KB Output is correct
11 Correct 42 ms 15964 KB Output is correct
12 Correct 91 ms 18232 KB Output is correct
13 Correct 45 ms 15964 KB Output is correct
14 Correct 46 ms 15964 KB Output is correct
15 Correct 754 ms 24904 KB Output is correct
16 Execution timed out 20034 ms 27916 KB Time limit exceeded
17 Halted 0 ms 0 KB -