Submission #2482

#	Time	Username	Problem	Language	Result	Execution time	Memory
2482		kriii	웜뱃 (IOI13_wombats)	C++98	55 / 100	20000 ms	26672 KiB

wombats

#include "wombats.h"
#define group_size 500

const int NON = 0x7fffffff;
int N, M, G, Start[30], End[30], Z = 32;

int ANS[200][200],GO[64][200][200],OUT[64],NOW[200],LEFT[200],RIGHT[200];
int HH[5000][200],VV[5000][200];

inline int min(int a, int b){return a < b ? a : b;}

void going(int i)
{
	int j;

	for (j=0;j<M;j++) LEFT[j] = RIGHT[j] = NOW[j];
	for (j=1;j<M;j++){
		if (LEFT[j-1] == NON) continue;
		LEFT[j] = min(LEFT[j],LEFT[j-1]+HH[i][j-1]);
	}
	for (j=M-2;j>=0;j--){
		if (RIGHT[j+1] == NON) continue;
		RIGHT[j] = min(RIGHT[j],RIGHT[j+1]+HH[i][j]);
	}

	for (j=0;j<M;j++){
		NOW[j] = min(NOW[j],LEFT[j]);
		NOW[j] = min(NOW[j],RIGHT[j]);
	}
}

void make()
{
	int i,j;

	for (i=0;i<M;i++){
		for (j=0;j<M;j++) NOW[j] = GO[1][i][j];
		going(N-1);
		for (j=0;j<M;j++) ANS[i][j] = NOW[j];
	}
}

void modify(int g)
{
	int i,j,k,x=g+Z,s;

	for (i=0;i<M;i++){
		for (j=0;j<M;j++) NOW[j] = NON;
		NOW[i] = 0;
		for (k=Start[g];k<End[g];k++){
			going(k);
			for (j=0;j<M;j++) NOW[j] += VV[k][j];
		}
		for (j=0;j<M;j++) GO[x][i][j] = NOW[j];
	}

	x /= 2; s = 1;
	while (x){
		if (OUT[x*2] > 0 || (OUT[x*2] == 0 && OUT[x*2+1] == s)) for (i=0;i<M;i++) for (j=0;j<M;j++) GO[x][i][j] = GO[x*2][i][j];
		else{
			for (i=0;i<M;i++) for (j=0;j<M;j++) GO[x][i][j] = NON;
			for (i=0;i<M;i++) for (j=0;j<M;j++) for (k=0;k<M;k++) GO[x][i][j] = min(GO[x][i][j],GO[x*2][i][k]+GO[x*2+1][k][j]);
		}
		x /= 2; s *= 2;
	}
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	N = R; M = C;
	G = (R + group_size - 1) / group_size; int i,j;
	for (i=0;i<G;i++){
		Start[i] = i * group_size;
		End[i] = (i + 1) * group_size;
	}
	if (End[G-1] >= R) End[G-1] = R-1;
	if (Start[G-1] == End[G-1]) G--;

	for (i=0;i<R;i++) for (j=0;j<C-1;j++) HH[i][j] = H[i][j];
	for (i=0;i<R-1;i++) for (j=0;j<C;j++) VV[i][j] = V[i][j];
	for (i=G;i<Z;i++) OUT[i+Z] = 1;
	for (i=Z-1;i>=1;i--) OUT[i] = OUT[i*2] + OUT[i*2+1];
	for (i=0;i<G;i++) modify(i);
	make();
}

void changeH(int P, int Q, int W) {
	HH[P][Q] = W;
	modify(P/group_size);
	make();
}

void changeV(int P, int Q, int W) {
	VV[P][Q] = W;
	modify(P/group_size);
	make();
}

int escape(int V1, int V2) {
	return ANS[V1][V2];
}

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