oj.uz

Submission #227223

# Submission time Handle Problem Language Result Execution time Memory
227223 2020-04-26T14:25:53 Z kig9981 Wombats (IOI13_wombats) C++17
76 / 100
 9548 ms 101672 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]=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 46 ms 88312 KB Output is correct
2 Correct 47 ms 88312 KB Output is correct
3 Correct 137 ms 89976 KB Output is correct
4 Correct 49 ms 88312 KB Output is correct
5 Correct 51 ms 88312 KB Output is correct
6 Correct 43 ms 80508 KB Output is correct
7 Correct 43 ms 80504 KB Output is correct
8 Correct 48 ms 80504 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 80504 KB Output is correct
2 Correct 41 ms 80504 KB Output is correct
3 Correct 41 ms 80504 KB Output is correct
4 Correct 45 ms 80632 KB Output is correct
5 Correct 53 ms 80632 KB Output is correct
6 Correct 49 ms 80640 KB Output is correct
7 Correct 43 ms 80640 KB Output is correct
8 Correct 45 ms 80632 KB Output is correct
9 Correct 45 ms 80632 KB Output is correct
10 Correct 45 ms 80632 KB Output is correct
11 Correct 132 ms 81632 KB Output is correct
12 Correct 45 ms 80636 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1219 ms 81148 KB Output is correct
2 Correct 1117 ms 81120 KB Output is correct
3 Correct 1287 ms 81144 KB Output is correct
4 Correct 1207 ms 81272 KB Output is correct
5 Correct 1240 ms 81016 KB Output is correct
6 Correct 41 ms 80504 KB Output is correct
7 Correct 41 ms 80512 KB Output is correct
8 Correct 41 ms 80504 KB Output is correct
9 Correct 5105 ms 81028 KB Output is correct
10 Correct 41 ms 80504 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 100088 KB Output is correct
2 Correct 55 ms 100088 KB Output is correct
3 Correct 55 ms 100088 KB Output is correct
4 Correct 96 ms 100856 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1187 ms 81020 KB Output is correct
2 Correct 1130 ms 80888 KB Output is correct
3 Correct 1275 ms 81148 KB Output is correct
4 Correct 1214 ms 81084 KB Output is correct
5 Correct 1250 ms 81148 KB Output is correct
6 Correct 54 ms 100088 KB Output is correct
7 Correct 53 ms 100088 KB Output is correct
8 Correct 64 ms 100088 KB Output is correct
9 Correct 96 ms 100984 KB Output is correct
10 Correct 51 ms 88312 KB Output is correct
11 Correct 45 ms 88312 KB Output is correct
12 Correct 124 ms 90104 KB Output is correct
13 Correct 47 ms 88312 KB Output is correct
14 Correct 47 ms 88312 KB Output is correct
15 Correct 49 ms 80504 KB Output is correct
16 Correct 43 ms 80504 KB Output is correct
17 Correct 48 ms 80504 KB Output is correct
18 Correct 45 ms 80632 KB Output is correct
19 Correct 46 ms 80636 KB Output is correct
20 Correct 45 ms 80632 KB Output is correct
21 Correct 52 ms 80632 KB Output is correct
22 Correct 51 ms 80632 KB Output is correct
23 Correct 44 ms 80620 KB Output is correct
24 Correct 45 ms 80632 KB Output is correct
25 Correct 133 ms 81788 KB Output is correct
26 Correct 44 ms 80632 KB Output is correct
27 Correct 5186 ms 81028 KB Output is correct
28 Correct 7162 ms 100772 KB Output is correct
29 Correct 7500 ms 97476 KB Output is correct
30 Correct 7523 ms 97208 KB Output is correct
31 Correct 7381 ms 101672 KB Output is correct
32 Correct 48 ms 80504 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1197 ms 81016 KB Output is correct
2 Correct 1136 ms 81228 KB Output is correct
3 Correct 1326 ms 81144 KB Output is correct
4 Correct 1247 ms 81028 KB Output is correct
5 Correct 1297 ms 81144 KB Output is correct
6 Correct 61 ms 100088 KB Output is correct
7 Correct 60 ms 100220 KB Output is correct
8 Correct 56 ms 100092 KB Output is correct
9 Correct 96 ms 100856 KB Output is correct
10 Correct 51 ms 88312 KB Output is correct
11 Correct 46 ms 88312 KB Output is correct
12 Correct 124 ms 89976 KB Output is correct
13 Correct 47 ms 88312 KB Output is correct
14 Correct 47 ms 88312 KB Output is correct
15 Incorrect 9548 ms 100128 KB Output isn't correct
16 Halted 0 ms 0 KB -