oj.uz

Submission #52017

# Submission time Handle Problem Language Result Execution time Memory
52017 2018-06-23T09:10:19 Z radoslav11 Wombats (IOI13_wombats) C++14
100 / 100
 7852 ms 237056 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 = 10;
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 tmp2, tr[1500];

void init(int l, int r, int idx)
{
	if(r - l <= B)
	{
		for(int ll = l; ll <= r; ll++)
		{
			for(int i = 0; i < m; i++)
			{
				tmp2[i][i] = 0;
				for(int o = i + 1; o < m; o++) tmp2[i][o] = tmp2[i][o - 1] + H[ll][o - 1];
				for(int o = i - 1; o >= 0; o--) tmp2[i][o] = tmp2[i][o + 1] + H[ll][o];
				for(int j = 0; j < m; j++) tmp2[i][j] += V[ll][j];
			}

			if(ll == l) tr[idx] = tmp2;
			else tr[idx] = merge(tr[idx], tmp2);
		}

		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)
	{
		for(int ll = l; ll <= r; ll++)
		{
			for(int i = 0; i < m; i++)
			{
				tmp2[i][i] = 0;
				for(int o = i + 1; o < m; o++) tmp2[i][o] = tmp2[i][o - 1] + H[ll][o - 1];
				for(int o = i - 1; o >= 0; o--) tmp2[i][o] = tmp2[i][o + 1] + H[ll][o];
				for(int j = 0; j < m; j++) tmp2[i][j] += V[ll][j];
			}

			if(ll == l) tr[idx] = tmp2;
			else tr[idx] = merge(tr[idx], tmp2);
		}

		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 - 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 577 ms 179156 KB Output is correct
2 Correct 609 ms 179176 KB Output is correct
3 Correct 641 ms 180684 KB Output is correct
4 Correct 556 ms 180684 KB Output is correct
5 Correct 560 ms 180684 KB Output is correct
6 Correct 3 ms 180684 KB Output is correct
7 Correct 2 ms 180684 KB Output is correct
8 Correct 2 ms 180684 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 180684 KB Output is correct
2 Correct 137 ms 180684 KB Output is correct
3 Correct 165 ms 180684 KB Output is correct
4 Correct 164 ms 180684 KB Output is correct
5 Correct 158 ms 180684 KB Output is correct
6 Correct 2 ms 180684 KB Output is correct
7 Correct 3 ms 180684 KB Output is correct
8 Correct 3 ms 180684 KB Output is correct
9 Correct 666 ms 180684 KB Output is correct
10 Correct 3 ms 180684 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 188140 KB Output is correct
2 Correct 601 ms 188148 KB Output is correct
3 Correct 569 ms 188236 KB Output is correct
4 Correct 593 ms 188844 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 188844 KB Output is correct
2 Correct 137 ms 188844 KB Output is correct
3 Correct 163 ms 188844 KB Output is correct
4 Correct 173 ms 188844 KB Output is correct
5 Correct 173 ms 188844 KB Output is correct
6 Correct 565 ms 188844 KB Output is correct
7 Correct 538 ms 188844 KB Output is correct
8 Correct 575 ms 188844 KB Output is correct
9 Correct 605 ms 188996 KB Output is correct
10 Correct 590 ms 188996 KB Output is correct
11 Correct 551 ms 188996 KB Output is correct
12 Correct 673 ms 188996 KB Output is correct
13 Correct 614 ms 188996 KB Output is correct
14 Correct 533 ms 188996 KB Output is correct
15 Correct 3 ms 188996 KB Output is correct
16 Correct 2 ms 188996 KB Output is correct
17 Correct 3 ms 188996 KB Output is correct
18 Correct 4 ms 188996 KB Output is correct
19 Correct 5 ms 188996 KB Output is correct
20 Correct 6 ms 188996 KB Output is correct
21 Correct 4 ms 188996 KB Output is correct
22 Correct 5 ms 188996 KB Output is correct
23 Correct 4 ms 188996 KB Output is correct
24 Correct 4 ms 188996 KB Output is correct
25 Correct 80 ms 188996 KB Output is correct
26 Correct 4 ms 188996 KB Output is correct
27 Correct 575 ms 188996 KB Output is correct
28 Correct 2107 ms 189196 KB Output is correct
29 Correct 2118 ms 189196 KB Output is correct
30 Correct 2140 ms 189196 KB Output is correct
31 Correct 2147 ms 191324 KB Output is correct
32 Correct 3 ms 191324 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 191324 KB Output is correct
2 Correct 147 ms 191324 KB Output is correct
3 Correct 208 ms 191324 KB Output is correct
4 Correct 181 ms 191324 KB Output is correct
5 Correct 166 ms 191324 KB Output is correct
6 Correct 571 ms 191324 KB Output is correct
7 Correct 564 ms 191324 KB Output is correct
8 Correct 602 ms 191324 KB Output is correct
9 Correct 580 ms 191324 KB Output is correct
10 Correct 536 ms 191324 KB Output is correct
11 Correct 568 ms 191324 KB Output is correct
12 Correct 670 ms 191324 KB Output is correct
13 Correct 578 ms 191324 KB Output is correct
14 Correct 588 ms 191324 KB Output is correct
15 Correct 2495 ms 191324 KB Output is correct
16 Correct 7852 ms 192112 KB Output is correct
17 Correct 3 ms 192112 KB Output is correct
18 Correct 3 ms 192112 KB Output is correct
19 Correct 2 ms 192112 KB Output is correct
20 Correct 4 ms 192112 KB Output is correct
21 Correct 5 ms 192112 KB Output is correct
22 Correct 3 ms 192112 KB Output is correct
23 Correct 4 ms 192112 KB Output is correct
24 Correct 4 ms 192112 KB Output is correct
25 Correct 4 ms 192112 KB Output is correct
26 Correct 4 ms 192112 KB Output is correct
27 Correct 86 ms 192112 KB Output is correct
28 Correct 4 ms 192112 KB Output is correct
29 Correct 646 ms 192112 KB Output is correct
30 Correct 2116 ms 192112 KB Output is correct
31 Correct 6321 ms 192112 KB Output is correct
32 Correct 6434 ms 199560 KB Output is correct
33 Correct 2125 ms 199560 KB Output is correct
34 Correct 6694 ms 207056 KB Output is correct
35 Correct 2076 ms 209556 KB Output is correct
36 Correct 6613 ms 217688 KB Output is correct
37 Correct 2537 ms 225380 KB Output is correct
38 Correct 6538 ms 233568 KB Output is correct
39 Correct 4 ms 233568 KB Output is correct
40 Correct 6868 ms 237056 KB Output is correct