oj.uz

Submission #227330

# Submission time Handle Problem Language Result Execution time Memory
227330 2020-04-27T01:39:17 Z kig9981 Wombats (IOI13_wombats) C++17
100 / 100
 4005 ms 189696 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=10, SZ=1<<9;
int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], P[200][200], md[SZ], D[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 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]+=V[b*B+i-1][j];
			}
			else {
				for(int j=0;j<M;j++) D[j]=(r!=j)*0x3fffffff;
			}
			for(int j=1;j<M;j++) D[j]=min(D[j],D[j-1]+H[b*B+i][j-1]);
			for(int j=M-2;j>=0;j--) D[j]=min(D[j],D[j+1]+H[b*B+i][j]);
		}
		for(int j=0;j<M;j++) tree[SZ+b][r][j]=D[j];
	}
}
 
void combine(int p, int l, int r)
{
	for(int i=0;i<M;i++) {
		P[i][i]=0;
		for(int j=1;j<M;j++) if(tree[l][i][P[i][i]]+V[md[p]][P[i][i]]+tree[r][P[i][i]][i]>=tree[l][i][j]+V[md[p]][j]+tree[r][j][i]) P[i][i]=j;
		tree[p][i][i]=tree[l][i][P[i][i]]+V[md[p]][P[i][i]]+tree[r][P[i][i]][i];
	}
	for(int i=1;i<M;i++) for(int j=0;j+i<M;j++) {
		P[j][j+i]=P[j][j+i-1];
		P[j+i][j]=P[j+i-1][j];
		for(int k=P[j][j+i-1]+1;k<=P[j+1][j+i];k++) if(tree[l][j][P[j][j+i]]+V[md[p]][P[j][j+i]]+tree[r][P[j][j+i]][j+i]>=tree[l][j][k]+V[md[p]][k]+tree[r][k][j+i]) P[j][j+i]=k;
		for(int k=P[j+i-1][j]+1;k<=P[j+i][j+1];k++) if(tree[l][j+i][P[j+i][j]]+V[md[p]][P[j+i][j]]+tree[r][P[j+i][j]][j]>=tree[l][j+i][k]+V[md[p]][k]+tree[r][k][j]) P[j+i][j]=k;
		tree[p][j][j+i]=tree[l][j][P[j][j+i]]+V[md[p]][P[j][j+i]]+tree[r][P[j][j+i]][j+i];
		tree[p][j+i][j]=tree[l][j+i][P[j+i][j]]+V[md[p]][P[j+i][j]]+tree[r][P[j+i][j]][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-1;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 82 ms 168440 KB Output is correct
2 Correct 85 ms 168440 KB Output is correct
3 Correct 161 ms 169976 KB Output is correct
4 Correct 85 ms 168440 KB Output is correct
5 Correct 85 ms 168440 KB Output is correct
6 Correct 80 ms 160580 KB Output is correct
7 Correct 78 ms 160504 KB Output is correct
8 Correct 79 ms 160632 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 160632 KB Output is correct
2 Correct 78 ms 160632 KB Output is correct
3 Correct 92 ms 160632 KB Output is correct
4 Correct 84 ms 160760 KB Output is correct
5 Correct 83 ms 160760 KB Output is correct
6 Correct 82 ms 160760 KB Output is correct
7 Correct 81 ms 160760 KB Output is correct
8 Correct 83 ms 160764 KB Output is correct
9 Correct 83 ms 160760 KB Output is correct
10 Correct 82 ms 160760 KB Output is correct
11 Correct 170 ms 161740 KB Output is correct
12 Correct 84 ms 160760 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 161144 KB Output is correct
2 Correct 300 ms 161180 KB Output is correct
3 Correct 325 ms 161144 KB Output is correct
4 Correct 309 ms 161304 KB Output is correct
5 Correct 299 ms 161144 KB Output is correct
6 Correct 78 ms 160632 KB Output is correct
7 Correct 78 ms 160632 KB Output is correct
8 Correct 82 ms 160632 KB Output is correct
9 Correct 790 ms 161272 KB Output is correct
10 Correct 78 ms 160632 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 180144 KB Output is correct
2 Correct 90 ms 180220 KB Output is correct
3 Correct 90 ms 180216 KB Output is correct
4 Correct 132 ms 180984 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 161144 KB Output is correct
2 Correct 289 ms 161400 KB Output is correct
3 Correct 302 ms 161144 KB Output is correct
4 Correct 302 ms 161148 KB Output is correct
5 Correct 306 ms 161272 KB Output is correct
6 Correct 92 ms 180216 KB Output is correct
7 Correct 89 ms 180216 KB Output is correct
8 Correct 94 ms 180216 KB Output is correct
9 Correct 136 ms 180984 KB Output is correct
10 Correct 96 ms 168440 KB Output is correct
11 Correct 94 ms 168440 KB Output is correct
12 Correct 166 ms 170104 KB Output is correct
13 Correct 84 ms 168440 KB Output is correct
14 Correct 86 ms 168440 KB Output is correct
15 Correct 91 ms 160636 KB Output is correct
16 Correct 78 ms 160636 KB Output is correct
17 Correct 91 ms 160632 KB Output is correct
18 Correct 84 ms 160760 KB Output is correct
19 Correct 83 ms 160716 KB Output is correct
20 Correct 97 ms 160760 KB Output is correct
21 Correct 84 ms 160760 KB Output is correct
22 Correct 92 ms 160760 KB Output is correct
23 Correct 82 ms 160760 KB Output is correct
24 Correct 82 ms 160760 KB Output is correct
25 Correct 167 ms 161784 KB Output is correct
26 Correct 85 ms 160888 KB Output is correct
27 Correct 805 ms 161272 KB Output is correct
28 Correct 997 ms 180856 KB Output is correct
29 Correct 1077 ms 177276 KB Output is correct
30 Correct 1110 ms 177272 KB Output is correct
31 Correct 1037 ms 181656 KB Output is correct
32 Correct 81 ms 160636 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 161208 KB Output is correct
2 Correct 298 ms 161272 KB Output is correct
3 Correct 303 ms 161144 KB Output is correct
4 Correct 300 ms 161144 KB Output is correct
5 Correct 317 ms 161272 KB Output is correct
6 Correct 93 ms 180220 KB Output is correct
7 Correct 103 ms 180216 KB Output is correct
8 Correct 91 ms 180216 KB Output is correct
9 Correct 131 ms 180988 KB Output is correct
10 Correct 96 ms 168440 KB Output is correct
11 Correct 96 ms 168440 KB Output is correct
12 Correct 166 ms 170104 KB Output is correct
13 Correct 100 ms 168440 KB Output is correct
14 Correct 84 ms 168440 KB Output is correct
15 Correct 1334 ms 180476 KB Output is correct
16 Correct 3831 ms 182188 KB Output is correct
17 Correct 80 ms 160632 KB Output is correct
18 Correct 93 ms 160632 KB Output is correct
19 Correct 79 ms 160632 KB Output is correct
20 Correct 84 ms 160764 KB Output is correct
21 Correct 83 ms 160760 KB Output is correct
22 Correct 83 ms 160760 KB Output is correct
23 Correct 96 ms 160760 KB Output is correct
24 Correct 83 ms 160760 KB Output is correct
25 Correct 82 ms 160764 KB Output is correct
26 Correct 95 ms 160760 KB Output is correct
27 Correct 190 ms 163320 KB Output is correct
28 Correct 89 ms 160760 KB Output is correct
29 Correct 804 ms 161292 KB Output is correct
30 Correct 998 ms 184696 KB Output is correct
31 Correct 3306 ms 189204 KB Output is correct
32 Correct 3264 ms 188956 KB Output is correct
33 Correct 1033 ms 180664 KB Output is correct
34 Correct 3602 ms 184908 KB Output is correct
35 Correct 1138 ms 180728 KB Output is correct
36 Correct 3834 ms 184996 KB Output is correct
37 Correct 1035 ms 186232 KB Output is correct
38 Correct 3315 ms 189696 KB Output is correct
39 Correct 79 ms 160632 KB Output is correct
40 Correct 4005 ms 185124 KB Output is correct