oj.uz

Submission #227324

# Submission time Handle Problem Language Result Execution time Memory
227324 2020-04-27T00:35:24 Z kig9981 Wombats (IOI13_wombats) C++17
76 / 100
 9745 ms 186272 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], 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]=min(tree[l][b][m]+V[md[p]][m]+tree[r][m][m2],0x3f3f3f3f);
	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 86 ms 168568 KB Output is correct
2 Correct 83 ms 168440 KB Output is correct
3 Correct 165 ms 170104 KB Output is correct
4 Correct 91 ms 168468 KB Output is correct
5 Correct 85 ms 168444 KB Output is correct
6 Correct 79 ms 160632 KB Output is correct
7 Correct 79 ms 160632 KB Output is correct
8 Correct 80 ms 160632 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 160760 KB Output is correct
2 Correct 80 ms 160632 KB Output is correct
3 Correct 79 ms 160632 KB Output is correct
4 Correct 87 ms 160760 KB Output is correct
5 Correct 87 ms 160760 KB Output is correct
6 Correct 93 ms 160888 KB Output is correct
7 Correct 88 ms 160760 KB Output is correct
8 Correct 94 ms 160764 KB Output is correct
9 Correct 88 ms 160760 KB Output is correct
10 Correct 85 ms 160760 KB Output is correct
11 Correct 167 ms 161720 KB Output is correct
12 Correct 86 ms 160760 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 888 ms 161144 KB Output is correct
2 Correct 842 ms 161272 KB Output is correct
3 Correct 935 ms 161188 KB Output is correct
4 Correct 903 ms 161272 KB Output is correct
5 Correct 904 ms 161272 KB Output is correct
6 Correct 80 ms 160632 KB Output is correct
7 Correct 81 ms 160632 KB Output is correct
8 Correct 80 ms 160636 KB Output is correct
9 Correct 3340 ms 161272 KB Output is correct
10 Correct 96 ms 160632 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 180288 KB Output is correct
2 Correct 95 ms 180216 KB Output is correct
3 Correct 95 ms 180216 KB Output is correct
4 Correct 148 ms 180984 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 895 ms 161148 KB Output is correct
2 Correct 860 ms 161276 KB Output is correct
3 Correct 955 ms 161272 KB Output is correct
4 Correct 900 ms 161272 KB Output is correct
5 Correct 903 ms 161240 KB Output is correct
6 Correct 98 ms 180336 KB Output is correct
7 Correct 102 ms 180216 KB Output is correct
8 Correct 98 ms 180264 KB Output is correct
9 Correct 135 ms 181624 KB Output is correct
10 Correct 89 ms 168440 KB Output is correct
11 Correct 89 ms 168568 KB Output is correct
12 Correct 172 ms 171256 KB Output is correct
13 Correct 87 ms 168440 KB Output is correct
14 Correct 91 ms 168568 KB Output is correct
15 Correct 81 ms 160632 KB Output is correct
16 Correct 82 ms 160636 KB Output is correct
17 Correct 81 ms 160632 KB Output is correct
18 Correct 101 ms 160760 KB Output is correct
19 Correct 88 ms 160760 KB Output is correct
20 Correct 89 ms 160760 KB Output is correct
21 Correct 102 ms 160760 KB Output is correct
22 Correct 87 ms 160760 KB Output is correct
23 Correct 89 ms 160760 KB Output is correct
24 Correct 88 ms 160760 KB Output is correct
25 Correct 169 ms 163064 KB Output is correct
26 Correct 88 ms 160760 KB Output is correct
27 Correct 3344 ms 161272 KB Output is correct
28 Correct 5334 ms 184468 KB Output is correct
29 Correct 5307 ms 180788 KB Output is correct
30 Correct 5286 ms 180600 KB Output is correct
31 Correct 5362 ms 186272 KB Output is correct
32 Correct 93 ms 160632 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 901 ms 161016 KB Output is correct
2 Correct 852 ms 161272 KB Output is correct
3 Correct 940 ms 161272 KB Output is correct
4 Correct 893 ms 161272 KB Output is correct
5 Correct 925 ms 161188 KB Output is correct
6 Correct 93 ms 180220 KB Output is correct
7 Correct 97 ms 180216 KB Output is correct
8 Correct 98 ms 180344 KB Output is correct
9 Correct 133 ms 181624 KB Output is correct
10 Correct 90 ms 168440 KB Output is correct
11 Correct 87 ms 168452 KB Output is correct
12 Correct 170 ms 171384 KB Output is correct
13 Correct 87 ms 168440 KB Output is correct
14 Correct 91 ms 168544 KB Output is correct
15 Incorrect 9745 ms 185516 KB Output isn't correct
16 Halted 0 ms 0 KB -