oj.uz

Submission #257663

# Submission time Handle Problem Language Result Execution time Memory
257663 2020-08-04T14:13:35 Z davi_bart Wombats (IOI13_wombats) C++14
28 / 100
 20000 ms 17920 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
typedef long long ll;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int h[5000][200],v[5000][200];
int ans[5000][200][200];
int r,c;
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;
    //calc();
}

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

void changeV(int P, int Q, int W) {
  v[P][Q]=W;
  //calc();
}
bool vis[5000][200];
int escape(int V1, int V2) {
  //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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 13056 KB Output is correct
2 Correct 73 ms 13056 KB Output is correct
3 Execution timed out 20091 ms 14740 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8192 KB Output is correct
2 Correct 6 ms 8192 KB Output is correct
3 Correct 5 ms 8192 KB Output is correct
4 Correct 22 ms 8192 KB Output is correct
5 Correct 12 ms 8192 KB Output is correct
6 Correct 22 ms 8192 KB Output is correct
7 Correct 33 ms 8192 KB Output is correct
8 Correct 33 ms 8192 KB Output is correct
9 Correct 41 ms 8192 KB Output is correct
10 Correct 32 ms 8192 KB Output is correct
11 Correct 15303 ms 9344 KB Output is correct
12 Correct 32 ms 8192 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 8436 KB Output is correct
2 Correct 205 ms 8872 KB Output is correct
3 Correct 272 ms 8448 KB Output is correct
4 Correct 268 ms 8520 KB Output is correct
5 Correct 260 ms 8568 KB Output is correct
6 Correct 5 ms 8192 KB Output is correct
7 Correct 6 ms 8192 KB Output is correct
8 Correct 5 ms 8192 KB Output is correct
9 Correct 239 ms 8696 KB Output is correct
10 Correct 7 ms 8192 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 942 ms 17020 KB Output is correct
2 Correct 1314 ms 17032 KB Output is correct
3 Correct 942 ms 17020 KB Output is correct
4 Execution timed out 20050 ms 17632 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 8440 KB Output is correct
2 Correct 212 ms 8892 KB Output is correct
3 Correct 270 ms 8568 KB Output is correct
4 Correct 271 ms 8448 KB Output is correct
5 Correct 265 ms 8448 KB Output is correct
6 Correct 940 ms 17216 KB Output is correct
7 Correct 1310 ms 17212 KB Output is correct
8 Correct 947 ms 17024 KB Output is correct
9 Execution timed out 20019 ms 17844 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 8320 KB Output is correct
2 Correct 212 ms 8892 KB Output is correct
3 Correct 266 ms 8448 KB Output is correct
4 Correct 268 ms 8568 KB Output is correct
5 Correct 260 ms 8448 KB Output is correct
6 Correct 944 ms 17144 KB Output is correct
7 Correct 1320 ms 17220 KB Output is correct
8 Correct 933 ms 17024 KB Output is correct
9 Execution timed out 20091 ms 17920 KB Time limit exceeded
10 Halted 0 ms 0 KB -