oj.uz

Submission #227210

# Submission time Handle Problem Language Result Execution time Memory
227210 2020-04-26T14:01:25 Z kig9981 Wombats (IOI13_wombats) C++17
76 / 100
 9623 ms 101880 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 dnc(int p, int l, int r, 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(tree[l][b][i]+V[md[p]][i]+tree[r][i][m2]<tree[l][b][m]+V[md[p]][m]+tree[r][m][m2]) m=i;
	tree[p][b][m2]=tree[l][b][m]+V[md[p]][m]+tree[r][m][m2];
	dnc(p,l,r,b,s1,m,s2,m2-1);
	dnc(p,l,r,b,m,e1,m2+1,e2);
}

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;) for(int j=0;j<M;j++) dnc(i,2*i,2*i+1,j,0,M-1,0,M-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;) for(int j=0;j<M;j++) dnc(n,2*n,2*n+1,j,0,M-1,0,M-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;) for(int j=0;j<M;j++) dnc(n,2*n,2*n+1,j,0,M-1,0,M-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 54 ms 88440 KB Output is correct
2 Correct 51 ms 88312 KB Output is correct
3 Correct 137 ms 90360 KB Output is correct
4 Correct 49 ms 88312 KB Output is correct
5 Correct 47 ms 88312 KB Output is correct
6 Correct 44 ms 80504 KB Output is correct
7 Correct 44 ms 80504 KB Output is correct
8 Correct 46 ms 80504 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 80504 KB Output is correct
2 Correct 42 ms 80504 KB Output is correct
3 Correct 43 ms 80504 KB Output is correct
4 Correct 47 ms 80632 KB Output is correct
5 Correct 57 ms 80632 KB Output is correct
6 Correct 52 ms 80536 KB Output is correct
7 Correct 47 ms 80632 KB Output is correct
8 Correct 53 ms 80632 KB Output is correct
9 Correct 46 ms 80632 KB Output is correct
10 Correct 46 ms 80640 KB Output is correct
11 Correct 131 ms 82040 KB Output is correct
12 Correct 46 ms 80632 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1197 ms 81016 KB Output is correct
2 Correct 1128 ms 81016 KB Output is correct
3 Correct 1260 ms 81016 KB Output is correct
4 Correct 1211 ms 81144 KB Output is correct
5 Correct 1243 ms 81148 KB Output is correct
6 Correct 51 ms 80504 KB Output is correct
7 Correct 43 ms 80500 KB Output is correct
8 Correct 43 ms 80504 KB Output is correct
9 Correct 5081 ms 81144 KB Output is correct
10 Correct 44 ms 80512 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 100088 KB Output is correct
2 Correct 56 ms 100220 KB Output is correct
3 Correct 58 ms 100168 KB Output is correct
4 Correct 112 ms 101240 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1192 ms 81016 KB Output is correct
2 Correct 1135 ms 81016 KB Output is correct
3 Correct 1278 ms 81148 KB Output is correct
4 Correct 1210 ms 81020 KB Output is correct
5 Correct 1239 ms 81024 KB Output is correct
6 Correct 57 ms 100088 KB Output is correct
7 Correct 56 ms 100064 KB Output is correct
8 Correct 58 ms 100088 KB Output is correct
9 Correct 97 ms 101240 KB Output is correct
10 Correct 48 ms 88312 KB Output is correct
11 Correct 48 ms 88388 KB Output is correct
12 Correct 132 ms 90360 KB Output is correct
13 Correct 49 ms 88312 KB Output is correct
14 Correct 51 ms 88312 KB Output is correct
15 Correct 44 ms 80512 KB Output is correct
16 Correct 42 ms 80492 KB Output is correct
17 Correct 42 ms 80504 KB Output is correct
18 Correct 53 ms 80632 KB Output is correct
19 Correct 46 ms 80632 KB Output is correct
20 Correct 46 ms 80632 KB Output is correct
21 Correct 53 ms 80552 KB Output is correct
22 Correct 45 ms 80640 KB Output is correct
23 Correct 47 ms 80632 KB Output is correct
24 Correct 45 ms 80632 KB Output is correct
25 Correct 133 ms 82044 KB Output is correct
26 Correct 47 ms 80632 KB Output is correct
27 Correct 5087 ms 81016 KB Output is correct
28 Correct 7078 ms 101188 KB Output is correct
29 Correct 7535 ms 97572 KB Output is correct
30 Correct 7511 ms 97228 KB Output is correct
31 Correct 7218 ms 101880 KB Output is correct
32 Correct 43 ms 80504 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1194 ms 81248 KB Output is correct
2 Correct 1125 ms 81016 KB Output is correct
3 Correct 1271 ms 81148 KB Output is correct
4 Correct 1223 ms 81152 KB Output is correct
5 Correct 1252 ms 81016 KB Output is correct
6 Correct 58 ms 100088 KB Output is correct
7 Correct 64 ms 100092 KB Output is correct
8 Correct 54 ms 100096 KB Output is correct
9 Correct 124 ms 101368 KB Output is correct
10 Correct 49 ms 88304 KB Output is correct
11 Correct 58 ms 88440 KB Output is correct
12 Correct 142 ms 90432 KB Output is correct
13 Correct 50 ms 88360 KB Output is correct
14 Correct 47 ms 88364 KB Output is correct
15 Incorrect 9623 ms 100704 KB Output isn't correct
16 Halted 0 ms 0 KB -