oj.uz

Submission #227215

# Submission time Handle Problem Language Result Execution time Memory
227215 2020-04-26T14:13:03 Z kig9981 Wombats (IOI13_wombats) C++17
39 / 100
 985 ms 100984 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=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 51 ms 88312 KB Output is correct
2 Correct 46 ms 88312 KB Output is correct
3 Correct 131 ms 90104 KB Output is correct
4 Correct 47 ms 88312 KB Output is correct
5 Correct 49 ms 88312 KB Output is correct
6 Correct 46 ms 80472 KB Output is correct
7 Correct 42 ms 80504 KB Output is correct
8 Correct 47 ms 80460 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 80376 KB Output is correct
2 Correct 41 ms 80512 KB Output is correct
3 Correct 42 ms 80504 KB Output is correct
4 Correct 43 ms 80632 KB Output is correct
5 Correct 48 ms 80640 KB Output is correct
6 Correct 49 ms 80632 KB Output is correct
7 Correct 48 ms 80632 KB Output is correct
8 Correct 43 ms 80632 KB Output is correct
9 Correct 42 ms 80632 KB Output is correct
10 Correct 43 ms 80632 KB Output is correct
11 Correct 128 ms 81784 KB Output is correct
12 Correct 45 ms 80632 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 971 ms 81016 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 54 ms 100096 KB Output is correct
2 Correct 56 ms 100088 KB Output is correct
3 Correct 60 ms 100088 KB Output is correct
4 Correct 104 ms 100984 KB Output is correct

Subtask #5
0 / 21.0

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

Subtask #6
0 / 24.0

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