oj.uz

답안 #204012

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
204012 2020-02-23T18:19:18 Z CaroLinda 웜뱃 (IOI13_wombats) C++14
12 / 100
 469 ms 21496 KB 
#include "wombats.h"
#include <bits/stdc++.h>

#define debug 
#define lp(i,a,b) for(int i = a ; i < b ; i++ )

const int DIV = 40 ;
const int inf = 1e9+10 ;
const int MAXN = 5005 ;
const int MAXM = 205 ;

using namespace std ;

int N , M ;
int ini_bucket[MAXN] , end_bucket[MAXN]; 
int my_block[MAXN ] ;
int resp[MAXM][MAXM] ;
int opt[MAXM][MAXM] ;
int h[MAXN][MAXM] ;
int v[MAXN][MAXM] ;
int tree[130*4][MAXM][MAXM] ;

//Esta funcao recebe um pedaco do meu grid maior
//Com esse pedaco, ela calcula a dp
//Stora o resultado na matriz resp[MAXM][MAXM]
void calc(int n_menor , int n_maior )
{

	if( n_menor == n_maior )
	{
		for(int i = 0 ; i < M ; i++ )
		{
			for(int j = 0  ; j < M ; j++ ) resp[i][j] = inf ;
			resp[i][i] = 0 ;
		}
		return;
	}

	int dp[MAXN][MAXM] ;

	for(int curr_c = 0; curr_c < M ; curr_c++ )
	{

		//Calculando a distancia de [n_menor][i] para [n_maior][j] , qualquer j

		lp(i,n_menor, n_maior + 1)
			lp(j,0,M) dp[i][j] = inf ;


		dp[n_menor][ curr_c ] = 0 ;

		for(int i = n_menor ; i <= n_maior ; i++ )
		{


			for(int j = 0 ; j < M ; j++ )
			{

				if( i > n_menor )
					dp[i][j] = min( dp[i][j] , dp[i-1][j] + v[i-1][j] ) ;

				if( j >= 1 )
					dp[i][j] = min( dp[i][j] , dp[i][j-1] + h[i][j-1] ) ;

			}

			for(int j = M-2 ; j >= 0 ; j-- )
				dp[i][j] = min( dp[i][j] , dp[i][j+1] + h[i][j] ) ;


		}



		for(int j = 0 ; j < M ; j++ )
			resp[ curr_c ][j] = dp[n_maior][j] ;

	}

}

int m(int l, int r) { return (l+r)>>1 ; }

void tres_colunas( int adj_left[][MAXM] ,int adj_right[][MAXM] )
{

	/*debug("Printando adj_left\n") ;
	for(int i = 0 ; i < M ; i++ , debug("\n") )
		for(int j = 0 ; j < M ; j++ ) debug("%d " , adj_left[i][j] ) ;
	debug("Printando adj_right\n") ;
	for(int i = 0 ; i < M ; i++ , debug("\n") )
		for(int j = 0 ; j < M ; j++ ) debug("%d " , adj_right[i][j] ) ;*/

	//opt(i-1,j) <= opt(i,j) <= opt(i,j+1)
	//opt(i,j+1) <= opt(i+1,j+1) <= opt(i+1,j+2)

	for(int diff = M-1 ;  diff >= 1-M ; diff -- )
	{

		for(int x = 0 ; x < M ; x++ )
		{
			int y = x + diff ;
			if( y >= M || y < 0 ) continue ;

			//debug("Calculating %d,%d\n", x , y ) ;

			//calc opt[x][y]


			int opt_min = 0 , opt_max = N-1 ;

			if( x-1 >= 0 ) opt_min = opt[x-1][y] ;
			if( y+1 < M ) opt_max = opt[x][y+1] ;

			int opt_val = inf ;

			for(int i = opt_min ; i <= opt_max ; i++ )
				if( adj_left[x][i] + adj_right[i][y]  < opt_val )
				{
					opt_val = adj_left[x][i] + adj_right[i][y] ;

					resp[x][y] = opt_val ;
					opt[x][y] = i ;
				}

		//	debug("Opt = %d\n\n", opt[x][y] ) ;

		}

	}

/*	debug("Printando resultado final\n") ;
	for(int i = 0 ; i < M ; i++ , debug("\n") )
		for(int j = 0 ; j < M ; j++ ) debug("%d " , resp[i][j] ) ;
	debug("\n") ;*/

}

int adj_aux[MAXM][MAXM] ;

void merge(int pos, int l, int r)
{

	int coluna_menor = end_bucket[ m(l,r) ] ;
	int coluna_maior = ini_bucket[ m(l,r)+1 ] ;

	calc(coluna_menor , coluna_maior ) ;

	for(int i = 0 ; i < M ; i++ )
		for(int j = 0 ; j < M ; j++ )
			adj_aux[i][j] = resp[i][j] ;

	tres_colunas( tree[pos*2] , adj_aux ) ;

	for(int i = 0 ; i < M ; i++ )
		for(int j = 0 ; j < M ; j++ )
			adj_aux[i][j] = resp[i][j] ;

	tres_colunas( adj_aux, tree[pos*2+1] ) ;

	for(int i = 0 ; i < M ; i++ )
		for(int j = 0 ; j < M ; j++ )
			tree[pos][i][j] = resp[i][j] ;

}

void build_seg(int pos, int l, int r)
{

	if( l == r )
	{

		calc( ini_bucket[l] , end_bucket[l] ) ;

		for(int i = 0 ; i < M ; i++ )
			for(int j = 0 ; j < M ; j++ )
				tree[pos][i][j] = resp[i][j] ;

		return ;

	}

	build_seg( pos*2,l, m(l,r) ) ;
	build_seg( pos*2+1, m(l,r)+1 , r ) ;

	merge(pos, l, r ) ;

}

void upd(int pos, int l, int r, int idx )
{

	if( l == r )
	{

		calc( ini_bucket[l] , end_bucket[l] ) ;

		for(int i = 0 ; i < M ; i++ )
			for(int j = 0 ; j < M ; j++ )
				tree[pos][i][j] = resp[i][j] ;

		return ;

	}

	if( idx <= m(l,r) ) upd(pos*2,l,m(l,r),idx );
	else upd(pos*2+1,m(l,r)+1, r, idx ) ;

	merge(pos,l,r) ;

}

inline void print()
{
	debug("Printing\n" ) ;
	for(int i = 0 ; i < M ; i++ , debug("\n") )
		for(int j = 0 ; j < M ; j++ ) debug("%d " , tree[1][i][j] ) ;
	debug("\n") ;
}

void init(int R, int C, int H[5000][200], int V[5000][200]) 
{
    
	N = R ;
	M = C ;

	for(int i = 0 ; i < N ; i++ )
		for(int j = 0 ; j < M ; j++ )
		{
			h[i][j] = H[i][j] ;
			v[i][j] = V[i][j] ;	
		}

	ini_bucket[1] = 0 ;

	for(int i = 0 , j = 0 , k = 1 ; i < N ; i++ , j++ )
	{

		if( j == DIV ) 
		{
			k++ ; 
			j = 0 ;
			ini_bucket[k] = i ;
		}

		my_block[i] = k ;
		end_bucket[k] = i ;

	}

	build_seg(1,1, my_block[N-1] ) ;


	for(int i = 0 ; i < M ; i++, debug("\n") )
		for(int j = 0 ; j < M ; j++ ) debug("%d " , resp[i][j] ) ;

}

void changeH(int P, int Q, int W) 
{
    h[P][Q] = W ;
    upd( 1 , 1 , my_block[ N-1 ] , my_block[P] ) ;
    //print() ;
}

void changeV(int P, int Q, int W) 
{
    v[P][Q] = W ;
    upd( 1 , 1,  my_block[N-1] , my_block[P] ) ;
    //print() ;
}

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: In function 'void print()':
wombats.cpp:215:23: warning: statement has no effect [-Wunused-value]
  debug("Printing\n" ) ;
                       ^
wombats.cpp:216:42: warning: right operand of comma operator has no effect [-Wunused-value]
  for(int i = 0 ; i < M ; i++ , debug("\n") )
                                          ^
wombats.cpp:217:59: warning: left operand of comma operator has no effect [-Wunused-value]
   for(int j = 0 ; j < M ; j++ ) debug("%d " , tree[1][i][j] ) ;
                                                           ^
wombats.cpp:218:14: warning: statement has no effect [-Wunused-value]
  debug("\n") ;
              ^
wombats.cpp: In function 'void init(int, int, int (*)[200], int (*)[200])':
wombats.cpp:254:41: warning: right operand of comma operator has no effect [-Wunused-value]
  for(int i = 0 ; i < M ; i++, debug("\n") )
                                         ^
wombats.cpp:255:56: warning: left operand of comma operator has no effect [-Wunused-value]
   for(int j = 0 ; j < M ; j++ ) debug("%d " , resp[i][j] ) ;
                                                        ^

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 17400 KB Output is correct
2 Incorrect 86 ms 17656 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Correct 97 ms 1528 KB Output is correct
12 Correct 5 ms 504 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 316 ms 1400 KB Output is correct
2 Correct 452 ms 1528 KB Output is correct
3 Correct 434 ms 1656 KB Output is correct
4 Correct 431 ms 1536 KB Output is correct
5 Incorrect 460 ms 1656 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 141 ms 21496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 328 ms 1508 KB Output is correct
2 Correct 456 ms 1564 KB Output is correct
3 Correct 431 ms 1556 KB Output is correct
4 Correct 433 ms 1528 KB Output is correct
5 Incorrect 469 ms 1528 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 319 ms 1400 KB Output is correct
2 Correct 448 ms 1528 KB Output is correct
3 Correct 435 ms 1592 KB Output is correct
4 Correct 429 ms 1532 KB Output is correct
5 Incorrect 458 ms 1528 KB Output isn't correct
6 Halted 0 ms 0 KB -