oj.uz

Submission #227327

# Submission time Handle Problem Language Result Execution time Memory
227327 2020-04-27T01:13:49 Z kig9981 Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 188512 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-1;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 85 ms 168568 KB Output is correct
2 Correct 85 ms 168544 KB Output is correct
3 Correct 167 ms 171256 KB Output is correct
4 Correct 85 ms 168440 KB Output is correct
5 Correct 83 ms 168312 KB Output is correct
6 Correct 84 ms 160760 KB Output is correct
7 Correct 79 ms 160632 KB Output is correct
8 Correct 78 ms 160632 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 160632 KB Output is correct
2 Correct 80 ms 160632 KB Output is correct
3 Correct 80 ms 160640 KB Output is correct
4 Correct 86 ms 160764 KB Output is correct
5 Correct 84 ms 160760 KB Output is correct
6 Correct 85 ms 160764 KB Output is correct
7 Correct 84 ms 160760 KB Output is correct
8 Correct 85 ms 160760 KB Output is correct
9 Correct 85 ms 160760 KB Output is correct
10 Correct 85 ms 160760 KB Output is correct
11 Correct 170 ms 163064 KB Output is correct
12 Correct 89 ms 160888 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 881 ms 161300 KB Output is correct
2 Correct 842 ms 161272 KB Output is correct
3 Correct 942 ms 161244 KB Output is correct
4 Correct 901 ms 161272 KB Output is correct
5 Correct 915 ms 161308 KB Output is correct
6 Correct 83 ms 160760 KB Output is correct
7 Correct 81 ms 160632 KB Output is correct
8 Correct 82 ms 160632 KB Output is correct
9 Correct 3361 ms 161276 KB Output is correct
10 Correct 89 ms 160632 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 180216 KB Output is correct
2 Correct 106 ms 180216 KB Output is correct
3 Correct 106 ms 180344 KB Output is correct
4 Correct 145 ms 181752 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 899 ms 161144 KB Output is correct
2 Correct 891 ms 161272 KB Output is correct
3 Correct 938 ms 161276 KB Output is correct
4 Correct 907 ms 161272 KB Output is correct
5 Correct 916 ms 161272 KB Output is correct
6 Correct 94 ms 180344 KB Output is correct
7 Correct 96 ms 180216 KB Output is correct
8 Correct 96 ms 180220 KB Output is correct
9 Correct 131 ms 181624 KB Output is correct
10 Correct 85 ms 168440 KB Output is correct
11 Correct 85 ms 168444 KB Output is correct
12 Correct 175 ms 171256 KB Output is correct
13 Correct 86 ms 168568 KB Output is correct
14 Correct 84 ms 168440 KB Output is correct
15 Correct 79 ms 160632 KB Output is correct
16 Correct 80 ms 160632 KB Output is correct
17 Correct 85 ms 160792 KB Output is correct
18 Correct 87 ms 160760 KB Output is correct
19 Correct 86 ms 160760 KB Output is correct
20 Correct 84 ms 160760 KB Output is correct
21 Correct 85 ms 160760 KB Output is correct
22 Correct 90 ms 160760 KB Output is correct
23 Correct 87 ms 160760 KB Output is correct
24 Correct 84 ms 160760 KB Output is correct
25 Correct 164 ms 163192 KB Output is correct
26 Correct 87 ms 160760 KB Output is correct
27 Correct 3349 ms 161320 KB Output is correct
28 Correct 5373 ms 182416 KB Output is correct
29 Correct 5332 ms 178648 KB Output is correct
30 Correct 5304 ms 178552 KB Output is correct
31 Correct 5355 ms 183248 KB Output is correct
32 Correct 80 ms 160632 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 874 ms 161272 KB Output is correct
2 Correct 837 ms 161400 KB Output is correct
3 Correct 925 ms 161144 KB Output is correct
4 Correct 900 ms 161148 KB Output is correct
5 Correct 899 ms 161272 KB Output is correct
6 Correct 92 ms 180216 KB Output is correct
7 Correct 91 ms 180344 KB Output is correct
8 Correct 93 ms 180344 KB Output is correct
9 Correct 132 ms 181624 KB Output is correct
10 Correct 86 ms 168440 KB Output is correct
11 Correct 86 ms 168444 KB Output is correct
12 Correct 172 ms 171384 KB Output is correct
13 Correct 85 ms 168440 KB Output is correct
14 Correct 84 ms 168440 KB Output is correct
15 Correct 9715 ms 183432 KB Output is correct
16 Execution timed out 20070 ms 188512 KB Time limit exceeded
17 Halted 0 ms 0 KB -