oj.uz

Submission #227323

# Submission time Handle Problem Language Result Execution time Memory
227323 2020-04-27T00:24:30 Z kig9981 Wombats (IOI13_wombats) C++17
39 / 100
 1002 ms 100812 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#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=20, SZ=1<<8;
int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], md[SZ], D[200], D2[200];

void set_md(int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	if(s==e) return;
	set_md(2*bit,s,m);
	set_md(2*bit+1,m+1,e);
	md[bit]=min((m+1)*B-1,N-1);
}

int get_cost(int h, int s, int e)
{
	if(s>e) swap(s,e);
	return PS[h][e]-PS[h][s];
}

void dnc(int h, 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]+get_cost(h,i,m2)<D[m]+get_cost(h,m,m2)) m=i;
	D2[m2]=D[m]+get_cost(h,m,m2);
	dnc(h,s1,m,s2,m2-1);
	dnc(h,m,e1,m2+1,e2);
}

void dijk(int b)
{
	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]=D2[j]+V[b*B+i-1][j];
			}
			else {
				for(int j=0;j<M;j++) D[j]=(r!=j)*0x3fffffff;
			}
			dnc(b*B+i,0,M-1,0,M-1);
		}
		for(int j=0;j<M;j++) tree[SZ+b][r][j]=D2[j];
	}
}

void combine(int p, int l, int r)
{
	for(int i=0;i<M;i++) {
		int k=0;
		for(int j=1;j<M;j++) if(tree[l][i][k]+V[md[p]][k]+tree[r][k][0]>=tree[l][i][j]+V[md[p]][j]+tree[r][j][0]) k=j;
		for(int j=0;j<M;j++) {
			while(k+1<M && tree[l][i][k]+V[md[p]][k]+tree[r][k][j]>=tree[l][i][k+1]+V[md[p]][k+1]+tree[r][k+1][j]) k++;
			tree[p][i][j]=tree[l][i][k]+V[md[p]][k]+tree[r][k][j];
		}
	}
}

void init(int R, int C, int (*H)[200], int (*V)[200])
{
	N=R; M=C; memset(tree,0x3f,sizeof(tree));
	for(int i=0;i<N;i++) for(int j=0;j<M-1;j++) {
		::H[i][j]=H[i][j];
		PS[i][j+1]=PS[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<SZ;i++) {
		if(i*B<N) dijk(i);
		else for(int j=0;j<M;j++) tree[SZ+i][j][j]=0;
	}
	set_md();
	for(int i=SZ;--i;) combine(i,2*i,2*i+1);
}

void changeH(int P, int Q, int W)
{
    H[P][Q]=W;
	for(int j=0;j<M;j++) PS[P][j+1]=PS[P][j]+H[P][j];
	dijk(P/B);
	for(int n=SZ+P/B;n>>=1;) combine(n,2*n,2*n+1);
}

void changeV(int P, int Q, int W)
{
    V[P][Q]=W;
	if(P/B==(P+1)/B) dijk(P/B);
	for(int n=SZ+P/B;n>>=1;) combine(n,2*n,2*n+1);
}

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

Compilation message

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 88312 KB Output is correct
2 Correct 48 ms 88312 KB Output is correct
3 Correct 129 ms 89976 KB Output is correct
4 Correct 51 ms 88312 KB Output is correct
5 Correct 48 ms 88312 KB Output is correct
6 Correct 44 ms 80504 KB Output is correct
7 Correct 43 ms 80504 KB Output is correct
8 Correct 45 ms 80508 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 80512 KB Output is correct
2 Correct 45 ms 80504 KB Output is correct
3 Correct 43 ms 80508 KB Output is correct
4 Correct 46 ms 80632 KB Output is correct
5 Correct 44 ms 80632 KB Output is correct
6 Correct 45 ms 80632 KB Output is correct
7 Correct 44 ms 80632 KB Output is correct
8 Correct 44 ms 80504 KB Output is correct
9 Correct 49 ms 80632 KB Output is correct
10 Correct 45 ms 80632 KB Output is correct
11 Correct 130 ms 81656 KB Output is correct
12 Correct 44 ms 80636 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 992 ms 80944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 100088 KB Output is correct
2 Correct 56 ms 100060 KB Output is correct
3 Correct 57 ms 100096 KB Output is correct
4 Correct 98 ms 100812 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1002 ms 81020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 998 ms 81144 KB Output isn't correct
2 Halted 0 ms 0 KB -