oj.uz

Submission #257669

# Submission time Handle Problem Language Result Execution time Memory
257669 2020-08-04T14:19:01 Z davi_bart Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 42892 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
typedef long long ll;
int h[5000][200],v[5000][200];
int ans[5000][200][200];
int r,c;
int mi=50;
struct node{
  int r,c,d,fin;
  bool operator<(const node &x)const {
    return d<x.d;
  }
  bool operator>(const node &x)const {
    return d>x.d;
  }
};
void calc(){
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      for(int x=0;x<c;x++)ans[i][j][x]=-1;
    }
  }
  priority_queue<node,vector<node>,greater<node> >q;
  for(int i=0;i<c;i++)q.push({r-1,i,0,i});
  while(!q.empty()){
    node x=q.top();
    q.pop();
    if(ans[x.r][x.c][x.fin]>=0)continue;
    ans[x.r][x.c][x.fin]=x.d;
    if(x.c>0)q.push({x.r,x.c-1,x.d+h[x.r][x.c-1],x.fin});
    if(x.c<c-1)q.push({x.r,x.c+1,x.d+h[x.r][x.c],x.fin});
    if(x.r>0)q.push({x.r-1,x.c,x.d+v[x.r-1][x.c],x.fin});
  }
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    for(int i=0;i<5000;i++){
      for(int j=0;j<200;j++){
        h[i][j]=H[i][j];
        v[i][j]=V[i][j];
      }
    }
    r=R;
    c=C;
    if(c<=mi)calc();
}

void changeH(int P, int Q, int W) {
  h[P][Q]=W;
  if(c<=mi)calc();
}

void changeV(int P, int Q, int W) {
  v[P][Q]=W;
  if(c<=mi)calc();
}
bool vis[5000][200];
int escape(int V1, int V2) {
  if(c<=mi)return ans[0][V1][V2];
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      vis[i][j]=0;
    }
  }
  priority_queue<node,vector<node>,greater<node> >q;
  q.push({r-1,V2,0,0});
  while(!q.empty()){
    node x=q.top();
    q.pop();
    if(vis[x.r][x.c])continue;
    vis[x.r][x.c]=1;
    if(x.r==0 && x.c==V1)return x.d;
    if(x.c>0)q.push({x.r,x.c-1,x.d+h[x.r][x.c-1],x.fin});
    if(x.c<c-1)q.push({x.r,x.c+1,x.d+h[x.r][x.c],x.fin});
    if(x.r>0)q.push({x.r-1,x.c,x.d+v[x.r-1][x.c],x.fin});
  }
}

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 33664 KB Output is correct
2 Correct 236 ms 33684 KB Output is correct
3 Correct 318 ms 35444 KB Output is correct
4 Correct 227 ms 33788 KB Output is correct
5 Correct 233 ms 33664 KB Output is correct
6 Correct 6 ms 8192 KB Output is correct
7 Correct 5 ms 8192 KB Output is correct
8 Correct 6 ms 8224 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8192 KB Output is correct
2 Correct 6 ms 8192 KB Output is correct
3 Correct 7 ms 8192 KB Output is correct
4 Correct 8 ms 8704 KB Output is correct
5 Correct 8 ms 8576 KB Output is correct
6 Correct 8 ms 8576 KB Output is correct
7 Correct 8 ms 8832 KB Output is correct
8 Correct 8 ms 8576 KB Output is correct
9 Correct 9 ms 8704 KB Output is correct
10 Correct 8 ms 8576 KB Output is correct
11 Correct 101 ms 9848 KB Output is correct
12 Correct 9 ms 8704 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 8516 KB Output is correct
2 Correct 216 ms 8944 KB Output is correct
3 Correct 282 ms 8520 KB Output is correct
4 Correct 280 ms 8528 KB Output is correct
5 Correct 270 ms 8448 KB Output is correct
6 Correct 5 ms 8192 KB Output is correct
7 Correct 5 ms 8192 KB Output is correct
8 Correct 5 ms 8192 KB Output is correct
9 Correct 258 ms 8696 KB Output is correct
10 Correct 5 ms 8192 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1440 ms 41440 KB Output is correct
2 Correct 1920 ms 41592 KB Output is correct
3 Correct 1380 ms 41496 KB Output is correct
4 Correct 1400 ms 42448 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 8568 KB Output is correct
2 Correct 207 ms 8876 KB Output is correct
3 Correct 272 ms 8448 KB Output is correct
4 Correct 268 ms 8516 KB Output is correct
5 Correct 270 ms 8448 KB Output is correct
6 Correct 1530 ms 41488 KB Output is correct
7 Correct 1934 ms 41388 KB Output is correct
8 Correct 1446 ms 41596 KB Output is correct
9 Correct 1436 ms 42892 KB Output is correct
10 Correct 222 ms 33656 KB Output is correct
11 Correct 221 ms 33664 KB Output is correct
12 Correct 310 ms 35528 KB Output is correct
13 Correct 226 ms 33656 KB Output is correct
14 Correct 226 ms 33784 KB Output is correct
15 Correct 6 ms 8192 KB Output is correct
16 Correct 6 ms 8192 KB Output is correct
17 Correct 5 ms 8192 KB Output is correct
18 Correct 8 ms 8704 KB Output is correct
19 Correct 8 ms 8576 KB Output is correct
20 Correct 7 ms 8704 KB Output is correct
21 Correct 9 ms 8832 KB Output is correct
22 Correct 9 ms 8576 KB Output is correct
23 Correct 8 ms 8704 KB Output is correct
24 Correct 11 ms 8576 KB Output is correct
25 Correct 98 ms 10108 KB Output is correct
26 Correct 8 ms 8704 KB Output is correct
27 Correct 255 ms 8552 KB Output is correct
28 Execution timed out 20087 ms 17528 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 8516 KB Output is correct
2 Correct 213 ms 8924 KB Output is correct
3 Correct 273 ms 8568 KB Output is correct
4 Correct 267 ms 8448 KB Output is correct
5 Correct 262 ms 8448 KB Output is correct
6 Correct 1532 ms 41352 KB Output is correct
7 Correct 1847 ms 41328 KB Output is correct
8 Correct 1457 ms 41420 KB Output is correct
9 Correct 1441 ms 42328 KB Output is correct
10 Correct 225 ms 33664 KB Output is correct
11 Correct 228 ms 33664 KB Output is correct
12 Correct 314 ms 35320 KB Output is correct
13 Correct 218 ms 33788 KB Output is correct
14 Correct 225 ms 33784 KB Output is correct
15 Correct 1286 ms 17168 KB Output is correct
16 Execution timed out 20042 ms 17272 KB Time limit exceeded
17 Halted 0 ms 0 KB -