Submission #227192

#	Time	Username	Problem	Language	Result	Execution time	Memory
227192		kig9981	Wombats (IOI13_wombats)	C++17	39 / 100	20090 ms	16812 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

const int B=1000;
int N, M, H[5000][200], V[5000][200], C[6][200][200], D[200], D2[200];

void dijk(int b)
{
	priority_queue<pair<int,int>> Q;
	for(int r=0;r<M;r++) {
		for(int i=0;i<B && b*B+i<N;i++) {
			if(i) {
				for(int j=0;j<M;j++) {
					D[j]+=V[b*B+i-1][j];
					Q.emplace(-D[j],j);
				}
			}
			else {
				for(int j=0;j<M;j++) {
					if(r==j) Q.emplace(D[j]=0,j);
					else D[j]=0x7fffffff;
				}
			}
			while(!Q.empty()) {
				auto[t,c]=Q.top();
				Q.pop();
				if(-t!=D[c]) continue;
				if(c && D[c-1]>D[c]+H[b*B+i][c-1]) {
					D[c-1]=D[c]+H[b*B+i][c-1];
					Q.emplace(-D[c-1],c-1);
				}
				if(c+1<M && D[c+1]>D[c]+H[b*B+i][c]) {
					D[c+1]=D[c]+H[b*B+i][c];
					Q.emplace(-D[c+1],c+1);
				}
			}
		}
		for(int j=0;j<M;j++) C[b][r][j]=D[j];
	}
}

void init(int R, int C, int (*H)[200], int (*V)[200])
{
	N=R; M=C;
	for(int i=0;i<N;i++) for(int j=0;j<M-1;j++) ::H[i][j]=H[i][j];
	for(int i=0;i<N-1;i++) for(int j=0;j<M;j++) ::V[i][j]=V[i][j];
	for(int i=0;i*B<N;i++) dijk(i);
}

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

void changeV(int P, int Q, int W)
{
    V[P][Q]=W;
	if(P/B==(P+1)/B) dijk(P/B);
}

void dnc(int b, int s1, int e1, int s2, int e2)
{
	int m2=(s2+e2)>>1, m=s1;
	if(s2>e2) return;
	for(int i=s1+1;i<=e1;i++) if(D[i]+C[b][i][m2]<D[m]+C[b][m][m2]) m=i;
	D2[m2]=D[m]+C[b][m][m2];
	dnc(b,s1,m,s2,m2-1);
	dnc(b,m,e1,m2+1,e2);
}

int escape(int V1, int V2)
{
	for(int b=0;b*B<N;b++) {
		if(b) {
			for(int j=0;j<M;j++) D[j]=D2[j]+V[b*B-1][j];
		}
		else {
			for(int j=0;j<M;j++) D[j]=(V1!=j)*0x3fffffff;
		}
		dnc(b,0,M-1,0,M-1);
	}
	return D2[V2];
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

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