oj.uz

Submission #227206

# Submission time Handle Problem Language Result Execution time Memory
227206 2020-04-26T13:49:13 Z kig9981 Wombats (IOI13_wombats) C++17
76 / 100
 12399 ms 61416 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=40, SZ=1<<7;
int N, M, H[5000][200], PS[5000][200], V[5001][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);
}
 
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 30 ms 48256 KB Output is correct
2 Correct 29 ms 48256 KB Output is correct
3 Correct 115 ms 49864 KB Output is correct
4 Correct 29 ms 48248 KB Output is correct
5 Correct 29 ms 48256 KB Output is correct
6 Correct 24 ms 40448 KB Output is correct
7 Correct 25 ms 40448 KB Output is correct
8 Correct 24 ms 40448 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 40448 KB Output is correct
2 Correct 24 ms 40448 KB Output is correct
3 Correct 24 ms 40448 KB Output is correct
4 Correct 27 ms 40448 KB Output is correct
5 Correct 27 ms 40448 KB Output is correct
6 Correct 27 ms 40576 KB Output is correct
7 Correct 27 ms 40448 KB Output is correct
8 Correct 26 ms 40448 KB Output is correct
9 Correct 26 ms 40448 KB Output is correct
10 Correct 26 ms 40576 KB Output is correct
11 Correct 110 ms 41464 KB Output is correct
12 Correct 27 ms 40448 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1402 ms 40960 KB Output is correct
2 Correct 1878 ms 40864 KB Output is correct
3 Correct 1991 ms 40996 KB Output is correct
4 Correct 1883 ms 40832 KB Output is correct
5 Correct 2108 ms 40876 KB Output is correct
6 Correct 25 ms 40448 KB Output is correct
7 Correct 25 ms 40448 KB Output is correct
8 Correct 25 ms 40448 KB Output is correct
9 Correct 8896 ms 40872 KB Output is correct
10 Correct 26 ms 40448 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 59896 KB Output is correct
2 Correct 38 ms 60032 KB Output is correct
3 Correct 39 ms 59932 KB Output is correct
4 Correct 87 ms 60792 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1401 ms 40952 KB Output is correct
2 Correct 1893 ms 40952 KB Output is correct
3 Correct 1980 ms 40952 KB Output is correct
4 Correct 1903 ms 40952 KB Output is correct
5 Correct 2109 ms 40952 KB Output is correct
6 Correct 37 ms 59904 KB Output is correct
7 Correct 38 ms 60024 KB Output is correct
8 Correct 38 ms 60032 KB Output is correct
9 Correct 80 ms 60792 KB Output is correct
10 Correct 30 ms 48248 KB Output is correct
11 Correct 29 ms 48256 KB Output is correct
12 Correct 116 ms 49912 KB Output is correct
13 Correct 32 ms 48248 KB Output is correct
14 Correct 30 ms 48256 KB Output is correct
15 Correct 24 ms 40440 KB Output is correct
16 Correct 25 ms 40448 KB Output is correct
17 Correct 24 ms 40448 KB Output is correct
18 Correct 27 ms 40448 KB Output is correct
19 Correct 26 ms 40520 KB Output is correct
20 Correct 26 ms 40576 KB Output is correct
21 Correct 26 ms 40448 KB Output is correct
22 Correct 26 ms 40448 KB Output is correct
23 Correct 27 ms 40568 KB Output is correct
24 Correct 26 ms 40448 KB Output is correct
25 Correct 110 ms 41592 KB Output is correct
26 Correct 27 ms 40576 KB Output is correct
27 Correct 8857 ms 40868 KB Output is correct
28 Correct 10984 ms 60460 KB Output is correct
29 Correct 12399 ms 56952 KB Output is correct
30 Correct 11822 ms 56872 KB Output is correct
31 Correct 11203 ms 61416 KB Output is correct
32 Correct 24 ms 40448 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1401 ms 41080 KB Output is correct
2 Correct 1868 ms 40952 KB Output is correct
3 Correct 1976 ms 40900 KB Output is correct
4 Correct 1893 ms 40952 KB Output is correct
5 Correct 2111 ms 40952 KB Output is correct
6 Correct 38 ms 59896 KB Output is correct
7 Correct 39 ms 60032 KB Output is correct
8 Correct 38 ms 59904 KB Output is correct
9 Correct 78 ms 60792 KB Output is correct
10 Correct 29 ms 48248 KB Output is correct
11 Correct 29 ms 48256 KB Output is correct
12 Correct 114 ms 49856 KB Output is correct
13 Correct 29 ms 48256 KB Output is correct
14 Correct 29 ms 48256 KB Output is correct
15 Incorrect 9648 ms 60012 KB Output isn't correct
16 Halted 0 ms 0 KB -