oj.uz

Submission #52011

# Submission time Handle Problem Language Result Execution time Memory
52011 2018-06-23T08:43:40 Z radoslav11 Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 231856 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 = 205;
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[1500];

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];

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

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

void changeV(int P, int Q, int W) 
{
    V[P][Q] = W;
	if(P < n - 1) recalc(P, 0, n - 2, 0);
	if(P) recalc(P - 1, 0, n - 2, 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 470 ms 179028 KB Output is correct
2 Correct 474 ms 179140 KB Output is correct
3 Correct 592 ms 180720 KB Output is correct
4 Correct 516 ms 180720 KB Output is correct
5 Correct 460 ms 180720 KB Output is correct
6 Correct 2 ms 180720 KB Output is correct
7 Correct 2 ms 180720 KB Output is correct
8 Correct 2 ms 180720 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 793 ms 180720 KB Output is correct
2 Correct 3445 ms 180720 KB Output is correct
3 Correct 922 ms 180720 KB Output is correct
4 Correct 848 ms 180720 KB Output is correct
5 Correct 870 ms 180720 KB Output is correct
6 Correct 3 ms 180720 KB Output is correct
7 Correct 2 ms 180720 KB Output is correct
8 Correct 2 ms 180720 KB Output is correct
9 Correct 14668 ms 180720 KB Output is correct
10 Correct 3 ms 180720 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 188244 KB Output is correct
2 Correct 504 ms 188244 KB Output is correct
3 Correct 518 ms 188296 KB Output is correct
4 Correct 505 ms 188860 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 842 ms 188860 KB Output is correct
2 Correct 3587 ms 188860 KB Output is correct
3 Correct 891 ms 188860 KB Output is correct
4 Correct 873 ms 188860 KB Output is correct
5 Correct 873 ms 188860 KB Output is correct
6 Correct 498 ms 188860 KB Output is correct
7 Correct 520 ms 188860 KB Output is correct
8 Correct 523 ms 188860 KB Output is correct
9 Correct 570 ms 189776 KB Output is correct
10 Correct 540 ms 189776 KB Output is correct
11 Correct 469 ms 189776 KB Output is correct
12 Correct 541 ms 189776 KB Output is correct
13 Correct 494 ms 189776 KB Output is correct
14 Correct 484 ms 189776 KB Output is correct
15 Correct 3 ms 189776 KB Output is correct
16 Correct 2 ms 189776 KB Output is correct
17 Correct 2 ms 189776 KB Output is correct
18 Correct 4 ms 189776 KB Output is correct
19 Correct 4 ms 189776 KB Output is correct
20 Correct 4 ms 189776 KB Output is correct
21 Correct 4 ms 189776 KB Output is correct
22 Correct 4 ms 189776 KB Output is correct
23 Correct 5 ms 189776 KB Output is correct
24 Correct 4 ms 189776 KB Output is correct
25 Correct 112 ms 189776 KB Output is correct
26 Correct 7 ms 189776 KB Output is correct
27 Correct 14689 ms 189776 KB Output is correct
28 Correct 15406 ms 197644 KB Output is correct
29 Correct 8279 ms 197644 KB Output is correct
30 Correct 6927 ms 197644 KB Output is correct
31 Execution timed out 20101 ms 208064 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 781 ms 208064 KB Output is correct
2 Correct 3267 ms 208064 KB Output is correct
3 Correct 840 ms 208064 KB Output is correct
4 Correct 828 ms 208064 KB Output is correct
5 Correct 850 ms 208064 KB Output is correct
6 Correct 499 ms 208064 KB Output is correct
7 Correct 461 ms 208064 KB Output is correct
8 Correct 490 ms 208064 KB Output is correct
9 Correct 566 ms 208064 KB Output is correct
10 Correct 453 ms 208064 KB Output is correct
11 Correct 452 ms 208064 KB Output is correct
12 Correct 533 ms 208064 KB Output is correct
13 Correct 494 ms 208064 KB Output is correct
14 Correct 495 ms 208064 KB Output is correct
15 Correct 4799 ms 220940 KB Output is correct
16 Execution timed out 20100 ms 231856 KB Time limit exceeded
17 Halted 0 ms 0 KB -