Submission #15672

#	Time	Username	Problem	Language	Result	Execution time	Memory
15672		progressive	Wombats (IOI13_wombats)	C++14	0 / 100	0 ms	262144 KiB

wombats

#include "wombats.h"
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
static const int bucket=2;
static const int MAXN=1<<12;
static const int MAXC=100;
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;
    //printf("%d\n",ind);
    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=i-imj;
        //  fprintf(stderr,"%d %d %d~%d\n",i,j,usedK[i+1][j],usedK[i+2][j+1]);
            idx[ind][i][j]=0x3f3f3f3f;
            int minK=-1;
            for(int K=usedK[i+1][j];K<=usedK[i+2][j+1];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];
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24