Submission #4590

#	Time	Username	Problem	Language	Result	Execution time	Memory
4590		cki86201	Wombats (IOI13_wombats)	C++98	37 / 100	12288 ms	18100 KiB

wombats

#include "wombats.h"
#include<stdlib.h>
#include<queue>
#include<vector>
#include<functional>
using namespace std;

#define X first
#define Y second

typedef pair<int,int> P;
typedef pair<int,P> Pi;

int H[5000][200],V[5000][200];
int T[5000],T2[2][5000][2];
int R,C;
bool check[5000][200];

//55point;

void build2()
{
	int i;
	T2[0][0][0]=0,T2[0][0][1]=H[0][0];
	for(i=1;i<R;i++){
		if(T2[0][i-1][0]>T2[0][i-1][1]){
			T2[0][i][1]=T2[0][i-1][1]+V[i-1][1];
			T2[0][i][0]=min(T2[0][i][1]+H[i][0],T2[0][i-1][0]+V[i-1][0]);
		}
		else{
			T2[0][i][0]=T2[0][i-1][0]+V[i-1][0];
			T2[0][i][1]=min(T2[0][i][0]+H[i][0],T2[0][i-1][1]+V[i-1][1]);
		}
	}
	T2[1][0][1]=0,T2[1][0][0]=H[0][0];
	for(i=1;i<R;i++){
		if(T2[1][i-1][0]>T2[1][i-1][1]){
			T2[1][i][1]=T2[1][i-1][1]+V[i-1][1];
			T2[1][i][0]=min(T2[1][i][1]+H[i][0],T2[1][i-1][0]+V[i-1][0]);
		}
		else{
			T2[1][i][0]=T2[1][i-1][0]+V[i-1][0];
			T2[1][i][1]=min(T2[1][i][0]+H[i][0],T2[1][i-1][1]+V[i-1][1]);
		}
	}
}

void init(int R, int C, int H_[5000][200], int V_[5000][200]){
	int i,j;
	for(i=0;i<R;i++)for(j=0;j<C-1;j++)H[i][j]=H_[i][j];
	for(i=0;i<R-1;i++)for(j=0;j<C;j++)V[i][j]=V_[i][j];
	::R=R;
	::C=C;
	if(C==1)for(i=1;i<R;i++)T[i]=T[i-1]+V[i-1][0];
	if(C==2)build2();
}

void changeH(int P, int Q, int W){
	H[P][Q]=W;
	if(C==2)build2();
}

void changeV(int P, int Q, int W) {
    V[P][Q]=W;
    if(C==1)for(int i=P+1;i<R;i++)T[i]=T[i-1]+V[i-1][0];
    if(C==2)build2();
}

int escape(int V1, int V2) {
	if(C==1)return T[R-1];
	if(C==2)return T2[V1][R-1][V2];
	priority_queue <Pi,vector<Pi>,greater<Pi> > pq;
	int i,j;
	for(i=0;i<R;i++)for(j=0;j<C;j++)check[i][j]=0;
	pq.push(Pi(0,P(0,V1)));
	while(!pq.empty()){
		Pi t=pq.top();
		pq.pop();
		if(check[t.Y.X][t.Y.Y])continue;
		check[t.Y.X][t.Y.Y]=1;
		if(t.Y.X == R-1 && t.Y.Y == V2)return t.X;
		if(t.Y.Y!=C-1 && !check[t.Y.X][t.Y.Y+1])pq.push(Pi(t.X+H[t.Y.X][t.Y.Y],P(t.Y.X,t.Y.Y+1)));
		if(t.Y.Y && !check[t.Y.X][t.Y.Y-1])pq.push(Pi(t.X+H[t.Y.X][t.Y.Y-1],P(t.Y.X,t.Y.Y-1)));
		if(t.Y.X!=R-1 && !check[t.Y.X+1][t.Y.Y])pq.push(Pi(t.X+V[t.Y.X][t.Y.Y],P(t.Y.X+1,t.Y.Y)));
	}
}

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