제출 #15661

#제출 시각아이디문제언어결과실행 시간메모리
15661progressive웜뱃 (IOI13_wombats)C++14
0 / 100
294 ms177060 KiB
#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[0][i]=0; 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...