#include "wombats.h"
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
static const int bucket=10;
static const int MAXN=1<<9;
static const int MAXC=200;
static int idx[2*MAXN][MAXC][MAXC]; //78.125MB
static int R;
static int C;
static int H[MAXN*bucket][MAXC];//3.90625MB
static int V[MAXN*bucket][MAXC];//3.90625MB
static void dijkFunction(int a)
{
int saveidx=a+MAXN;
int bias=a*bucket;
int dijk[bucket+1][MAXC];
if(bias>=R)
{
idx[saveidx][0][0]=-1;
return;
}
for(int i=0;i<C;i++)
{
memset(dijk,-1,sizeof(dijk) );
priority_queue<pair<int,pair<int,int> > > PQ;
PQ.push(make_pair(-0,make_pair(0,i)));
while(!PQ.empty())
{
int dist=-PQ.top().first;
int xcord=PQ.top().second.first;
int ycord=PQ.top().second.second;
PQ.pop();
if(dijk[xcord][ycord]!=-1) continue;
dijk[xcord][ycord]=dist;
if(xcord==bucket) continue;
if(xcord==R-bias) continue;
if(xcord!=R-bias-1) PQ.push(make_pair(-(dist+V[xcord+bias][ycord]),make_pair(xcord+1,ycord)));
if(ycord!=0)
PQ.push(make_pair(-(dist+H[xcord+bias][ycord-1]),make_pair(xcord,ycord-1)));
if(ycord!=C-1)
PQ.push(make_pair(-(dist+H[xcord+bias][ycord]),make_pair(xcord,ycord+1)));
}
for(int j=0;j<C;j++)
idx[saveidx][i][j]=dijk[min(R-1-bias,bucket)][j];
}
}
static void updateidx(int ind)
{
int ind1=ind*2, ind2=ind*2+1;
if(idx[ind2][0][0]<0)
{
for(int i=0;i<C;i++)
for(int j=0;j<C;j++)
idx[ind][i][j]=idx[ind1][i][j];
return;
}
int usedK[MAXC+2][MAXC+2];
for(int i=0;i<C+2;i++) usedK[i][0]=0;
for(int i=0;i<C+2;i++) usedK[0][i]=0;
for(int i=0;i<C+2;i++) usedK[C+1][i]=C-1;
for(int i=0;i<C+2;i++) usedK[i][C+1]=C-1;
for(int imj=C-1;imj>=1-C;imj--)
{
for(int i=max(imj,0);i<=min(C-1+imj,C-1);i++)
{
int j=j-imj;
idx[ind][i][j]=0x3f3f3f3f;
int minK=-1;
for(int K=usedK[i][j+1];K<=usedK[i+1][j+2];K++)
{
int val=idx[ind1][i][K]+idx[ind2][K][j];
if(idx[ind][i][j]>val)
{
idx[ind][i][j]=val;
minK=K;
}
}
usedK[i+1][j+1]=minK;
}
}
/*
//red herring
for(int i=0;i<C;i++)
for(int j=0;j<C;j++)
{
idx[ind][i][j]=0x3f3f3f3f;
for(int k=0;k<C;k++)
idx[ind][i][j]=min(idx[ind][i][j],idx[ind1][i][k]+idx[ind2][k][j]);
}
//*/
}
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-1;j++)
::H[i][j]=H[i][j];
for(int i=0;i<R-1;i++)
for(int j=0;j<C;j++)
::V[i][j]=V[i][j];
for(int i=0;i<MAXN;i++) dijkFunction(i);
for(int i=MAXN-1;i>0;i--)
updateidx(i);
}
static void refresh(int a)
{
dijkFunction(a);
a+=MAXN;
while(a!=1)
{
a/=2;
updateidx(a);
}
return;
}
void changeH(int P, int Q, int W)
{
int rbucket=P/bucket;
H[P][Q]=W;
refresh(rbucket);
}
void changeV(int P, int Q, int W)
{
int rbucket=P/bucket;
V[P][Q]=W;
refresh(rbucket);
}
int escape(int V1, int V2)
{
return idx[1][V1][V2];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
177056 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
177028 KB |
Output is correct - 6 tokens |
| 2 |
Correct |
0 ms |
177028 KB |
Output is correct - 6 tokens |
| 3 |
Correct |
0 ms |
177028 KB |
Output is correct - 6 tokens |
| 4 |
Runtime error |
4 ms |
177056 KB |
SIGSEGV Segmentation fault |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
287 ms |
177060 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
177056 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
288 ms |
177060 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
280 ms |
177056 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
