oj.uz

Submission #52003

# Submission time Handle Problem Language Result Execution time Memory
52003 2018-06-23T08:18:20 Z radoslav11 Wombats (IOI13_wombats) C++14
37 / 100
 7115 ms 185940 KB 
#include <bits/stdc++.h>
#include "wombats.h"
//#include "Lgrader.cpp"

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = 5002;
const int MAXM = 202;
const int B = 16;
const int inf = (int)1e9;

using matrix = array<array<int, MAXM>, MAXM>;

int n, m;
int H[MAXN + 42][MAXM + 42];
int V[MAXN + 42][MAXM + 42];
matrix tmp;
matrix dist[B + 3];
bool in_queue[MAXM][B + 3];

matrix bfs_brute(int l, int r)
{
	for(int ll = 0; ll < (r - l + 1); ll++)
		for(int i = 0; i < m; i++)
			for(int j = 0; j < m; j++)
				dist[ll][i][j] = inf;
	
	for(int st = 0; st < m; st++)
	{
		for(int i = 0; i < m; i++)
			for(int ll = 0; ll < (r - l + 1); ll++)
				in_queue[i][ll] = false;

		queue<pair<int, int> > Q;
		Q.push({st, 0});
		dist[0][st][st] = 0;
		in_queue[st][0] = true;

		while(!Q.empty())
		{
			int pos = Q.front().first, ll = Q.front().second;
			Q.pop(), in_queue[pos][ll] = false;
			
			if(pos && chkmin(dist[ll][st][pos - 1], dist[ll][st][pos] + H[ll + l][pos - 1]) && !in_queue[pos - 1][ll]) Q.push({pos - 1, ll}), in_queue[pos - 1][ll] = true; 
			if(pos < m - 1 && chkmin(dist[ll][st][pos + 1], dist[ll][st][pos] + H[ll + l][pos]) && !in_queue[pos + 1][ll]) Q.push({pos + 1, ll}), in_queue[pos + 1][ll] = true; 
			if(ll + l < r && chkmin(dist[ll + 1][st][pos], dist[ll][st][pos] + V[ll + l][pos]) && !in_queue[pos][ll + 1]) 
				Q.push({pos, ll + 1}), in_queue[pos][ll + 1] = true; 
		}
	}

	return dist[r - l];
}

int opt[MAXM][MAXN];

matrix merge(const matrix &f, const matrix &s)
{
	for(int i = 0; i < m; i++)
		for(int j = 0; j < m; j++)
			tmp[i][j] = inf;

	for(int j = 0; j < m; j++)
		for(int c = 0; c < m; c++)
			if(chkmin(tmp[0][j], f[0][c] + s[c][j]))
				opt[0][j] = c;

	for(int i = 1; i < m; i++)
	{
		opt[i][m] = m - 1;
		for(int j = m - 1; j >= 0; j--)
			for(int c = opt[i][j + 1]; c >= opt[i - 1][j]; c--)
				if(chkmin(tmp[i][j], f[i][c] + s[c][j]))
					opt[i][j] = c;
	}

	return tmp;
}

matrix tr[MAXN * 4 / B + 10];

void init(int l, int r, int idx)
{
	if(r - l <= B)
	{
		tr[idx] = bfs_brute(l, r + 1);
		return;
	}

	int mid = (l + r) >> 1;
	init(l, mid, 2 * idx + 1);
	init(mid + 1, r, 2 * idx + 2);
	tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
}

void recalc(int p, int l, int r, int idx)
{
	if(r - l <= B)
	{
		tr[idx] = bfs_brute(l, r + 1);
		return;
	}

	int mid = (l + r) >> 1;
	if(p <= mid) recalc(p, l, mid, 2 * idx + 1);
	else recalc(p, mid + 1, r, 2 * idx + 2);
	tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
}

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 - 1; j++)
			::H[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 < m - 1; i++) ::H[n][i] = inf;

	init(0, n - 1, 0);
}

void changeH(int P, int Q, int W) 
{
    H[P][Q] = W;
	recalc(P, 0, n - 1, 0);
}

void changeV(int P, int Q, int W) 
{
    V[P][Q] = W;
	recalc(P, 0, n - 1, 0);
}

int escape(int V1, int V2) 
{ 
	return tr[0][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 319 ms 174152 KB Output is correct
2 Correct 339 ms 174184 KB Output is correct
3 Correct 393 ms 175752 KB Output is correct
4 Correct 326 ms 175752 KB Output is correct
5 Correct 325 ms 175752 KB Output is correct
6 Correct 3 ms 175752 KB Output is correct
7 Correct 2 ms 175752 KB Output is correct
8 Correct 3 ms 175752 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 175752 KB Output is correct
2 Correct 3 ms 175752 KB Output is correct
3 Correct 3 ms 175752 KB Output is correct
4 Correct 4 ms 175752 KB Output is correct
5 Correct 4 ms 175752 KB Output is correct
6 Correct 5 ms 175752 KB Output is correct
7 Correct 4 ms 175752 KB Output is correct
8 Correct 5 ms 175752 KB Output is correct
9 Correct 4 ms 175752 KB Output is correct
10 Correct 4 ms 175752 KB Output is correct
11 Correct 91 ms 175752 KB Output is correct
12 Correct 6 ms 175752 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 175752 KB Output is correct
2 Correct 1938 ms 175752 KB Output is correct
3 Correct 476 ms 175752 KB Output is correct
4 Correct 478 ms 175752 KB Output is correct
5 Correct 432 ms 175752 KB Output is correct
6 Correct 2 ms 175752 KB Output is correct
7 Correct 3 ms 175752 KB Output is correct
8 Correct 2 ms 175752 KB Output is correct
9 Correct 7115 ms 175752 KB Output is correct
10 Correct 2 ms 175752 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 320 ms 185096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 185096 KB Output is correct
2 Correct 1750 ms 185096 KB Output is correct
3 Correct 474 ms 185096 KB Output is correct
4 Correct 433 ms 185096 KB Output is correct
5 Correct 463 ms 185096 KB Output is correct
6 Incorrect 306 ms 185488 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 185488 KB Output is correct
2 Correct 1748 ms 185488 KB Output is correct
3 Correct 437 ms 185488 KB Output is correct
4 Correct 430 ms 185488 KB Output is correct
5 Correct 438 ms 185488 KB Output is correct
6 Incorrect 316 ms 185940 KB Output isn't correct
7 Halted 0 ms 0 KB -