oj.uz

Submission #52007

# Submission time Handle Problem Language Result Execution time Memory
52007 2018-06-23T08:25:18 Z radoslav11 Wombats (IOI13_wombats) C++14
39 / 100
 20000 ms 41420 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 = 100;
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);
	//init(0, n - 1, 0);
}

void changeV(int P, int Q, int W) 
{
    V[P][Q] = W;
	recalc(P, 0, n - 1, 0);
	//init(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 127 ms 30968 KB Output is correct
2 Correct 129 ms 30968 KB Output is correct
3 Correct 198 ms 32488 KB Output is correct
4 Correct 137 ms 32488 KB Output is correct
5 Correct 129 ms 32488 KB Output is correct
6 Correct 2 ms 32488 KB Output is correct
7 Correct 2 ms 32488 KB Output is correct
8 Correct 2 ms 32488 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12112 ms 32488 KB Output is correct
2 Execution timed out 20068 ms 32488 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 39812 KB Output is correct
2 Correct 188 ms 40120 KB Output is correct
3 Correct 155 ms 40120 KB Output is correct
4 Correct 186 ms 41420 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12013 ms 41420 KB Output is correct
2 Execution timed out 20026 ms 41420 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12122 ms 41420 KB Output is correct
2 Execution timed out 20045 ms 41420 KB Time limit exceeded
3 Halted 0 ms 0 KB -