oj.uz

Submission #227214

# Submission time Handle Problem Language Result Execution time Memory
227214 2020-04-26T14:12:02 Z kig9981 Wombats (IOI13_wombats) C++17
Compilation error
 0 ms 0 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];

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 combine(int p, int l, int r)
{
	for(int i=0;i<M;i++) {
		int k=0;
		for(int j=0;j<M;j++) {
			while(k+1<M && tree[l][i][k]+V[md[p]][k]+tree[r][k][j]>tree[l][i][k+1]+V[md[p]][k+1]+tree[r][k+1][j]) k++;
			tree[p][i][j]=tree[l][i][k]+V[md[p]][k]+tree[r][k][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;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;
      ^~~
wombats.cpp:21:11: error: redefinition of 'const int B'
 const int B=20, SZ=1<<8;
           ^
wombats.cpp:18:11: note: 'const int B' previously defined here
 const int B=20, SZ=1<<8;
           ^
wombats.cpp:21:17: error: redefinition of 'const int SZ'
 const int B=20, SZ=1<<8;
                 ^~
wombats.cpp:18:17: note: 'const int SZ' previously defined here
 const int B=20, SZ=1<<8;
                 ^~
wombats.cpp:22:5: error: redefinition of 'int N'
 int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], md[SZ], D[200], D2[200];
     ^
wombats.cpp:19:5: note: 'int N' previously declared here
 int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], md[SZ], D[200], D2[200];
     ^
wombats.cpp:22:8: error: redefinition of 'int M'
 int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], md[SZ], D[200], D2[200];
        ^
wombats.cpp:19:8: note: 'int M' previously declared here
 int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], md[SZ], D[200], D2[200];
        ^
wombats.cpp:22:22: error: redefinition of 'int H [5000][200]'
 int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], md[SZ], D[200], D2[200];
                      ^
wombats.cpp:19:11: note: 'int H [5000][200]' previously declared here
 int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], md[SZ], D[200], D2[200];
           ^
wombats.cpp:22:37: error: redefinition of 'int PS [5000][200]'
 int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], md[SZ], D[200], D2[200];
                                     ^
wombats.cpp:19:25: note: 'int PS [5000][200]' previously declared here
 int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], md[SZ], D[200], D2[200];
                         ^~
wombats.cpp:22:51: error: redefinition of 'int V [5000][200]'
 int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], md[SZ], D[200], D2[200];
                                                   ^
wombats.cpp:19:40: note: 'int V [5000][200]' previously declared here
 int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], md[SZ], D[200], D2[200];
                                        ^
wombats.cpp:22:73: error: redefinition of 'int tree [512][200][200]'
 int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], md[SZ], D[200], D2[200];
                                                                         ^
wombats.cpp:19:54: note: 'int tree [512][200][200]' previously declared here
 int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], md[SZ], D[200], D2[200];
                                                      ^~~~
wombats.cpp:22:81: error: redefinition of 'int md [256]'
 int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], md[SZ], D[200], D2[200];
                                                                                 ^
wombats.cpp:19:76: note: 'int md [256]' previously declared here
 int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], md[SZ], D[200], D2[200];
                                                                            ^~
wombats.cpp:22:89: error: redefinition of 'int D [200]'
 int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], md[SZ], D[200], D2[200];
                                                                                         ^
wombats.cpp:19:84: note: 'int D [200]' previously declared here
 int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], md[SZ], D[200], D2[200];
                                                                                    ^
wombats.cpp:22:98: error: redefinition of 'int D2 [200]'
 int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], md[SZ], D[200], D2[200];
                                                                                                  ^
wombats.cpp:19:92: note: 'int D2 [200]' previously declared here
 int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], md[SZ], D[200], D2[200];
                                                                                            ^~