Submission #4588

#	Time	Username	Problem	Language	Result	Execution time	Memory
4588		cki86201	Wombats (IOI13_wombats)	C++98	28 / 100	20000 ms	18004 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 R,C;
bool check[5000][200];

//37point;

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;
}

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

void changeV(int P, int Q, int W) {
    V[P][Q]=W;
}

int escape(int V1, int 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(!check[t.Y.X][t.Y.Y+1] && t.Y.Y!=C-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(!check[t.Y.X+1][t.Y.Y] && t.Y.X!=R-1)pq.push(Pi(t.X+V[t.Y.X][t.Y.Y],P(t.Y.X+1,t.Y.Y)));
	}
}

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