oj.uz

답안 #52013

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
52013 2018-06-23T08:46:10 Z radoslav11 웜뱃 (IOI13_wombats) C++14
55 / 100
 20000 ms 203768 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 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

# 결과 실행 시간 메모리 Grader output
1 Correct 472 ms 179068 KB Output is correct
2 Correct 509 ms 179176 KB Output is correct
3 Correct 544 ms 180788 KB Output is correct
4 Correct 480 ms 180788 KB Output is correct
5 Correct 467 ms 180788 KB Output is correct
6 Correct 2 ms 180788 KB Output is correct
7 Correct 3 ms 180788 KB Output is correct
8 Correct 3 ms 180788 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 461 ms 180788 KB Output is correct
2 Correct 1033 ms 180788 KB Output is correct
3 Correct 500 ms 180788 KB Output is correct
4 Correct 504 ms 180788 KB Output is correct
5 Correct 543 ms 180788 KB Output is correct
6 Correct 3 ms 180788 KB Output is correct
7 Correct 3 ms 180788 KB Output is correct
8 Correct 2 ms 180788 KB Output is correct
9 Correct 4612 ms 180788 KB Output is correct
10 Correct 2 ms 180788 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 472 ms 188300 KB Output is correct
2 Correct 481 ms 188300 KB Output is correct
3 Correct 507 ms 188300 KB Output is correct
4 Correct 624 ms 188828 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 531 ms 188828 KB Output is correct
2 Correct 1046 ms 188828 KB Output is correct
3 Correct 519 ms 188828 KB Output is correct
4 Correct 477 ms 188828 KB Output is correct
5 Correct 472 ms 188828 KB Output is correct
6 Correct 474 ms 188828 KB Output is correct
7 Correct 467 ms 188828 KB Output is correct
8 Correct 495 ms 188828 KB Output is correct
9 Correct 514 ms 188948 KB Output is correct
10 Correct 464 ms 188948 KB Output is correct
11 Correct 461 ms 188948 KB Output is correct
12 Correct 542 ms 188948 KB Output is correct
13 Correct 535 ms 188948 KB Output is correct
14 Correct 457 ms 188948 KB Output is correct
15 Correct 2 ms 188948 KB Output is correct
16 Correct 2 ms 188948 KB Output is correct
17 Correct 2 ms 188948 KB Output is correct
18 Correct 3 ms 188948 KB Output is correct
19 Correct 3 ms 188948 KB Output is correct
20 Correct 3 ms 188948 KB Output is correct
21 Correct 4 ms 188948 KB Output is correct
22 Correct 3 ms 188948 KB Output is correct
23 Correct 3 ms 188948 KB Output is correct
24 Correct 3 ms 188948 KB Output is correct
25 Correct 81 ms 188948 KB Output is correct
26 Correct 5 ms 188948 KB Output is correct
27 Correct 4528 ms 188948 KB Output is correct
28 Correct 14244 ms 190044 KB Output is correct
29 Correct 4773 ms 190044 KB Output is correct
30 Correct 4680 ms 190044 KB Output is correct
31 Execution timed out 20082 ms 190116 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 470 ms 190116 KB Output is correct
2 Correct 1037 ms 190116 KB Output is correct
3 Correct 479 ms 190116 KB Output is correct
4 Correct 477 ms 190116 KB Output is correct
5 Correct 540 ms 190116 KB Output is correct
6 Correct 464 ms 190116 KB Output is correct
7 Correct 495 ms 190116 KB Output is correct
8 Correct 492 ms 190116 KB Output is correct
9 Correct 510 ms 190116 KB Output is correct
10 Correct 455 ms 190116 KB Output is correct
11 Correct 481 ms 190116 KB Output is correct
12 Correct 615 ms 190116 KB Output is correct
13 Correct 487 ms 190116 KB Output is correct
14 Correct 455 ms 190116 KB Output is correct
15 Correct 4898 ms 191208 KB Output is correct
16 Correct 19957 ms 192760 KB Output is correct
17 Correct 3 ms 192760 KB Output is correct
18 Correct 2 ms 192760 KB Output is correct
19 Correct 3 ms 192760 KB Output is correct
20 Correct 3 ms 192760 KB Output is correct
21 Correct 3 ms 192760 KB Output is correct
22 Correct 3 ms 192760 KB Output is correct
23 Correct 4 ms 192760 KB Output is correct
24 Correct 3 ms 192760 KB Output is correct
25 Correct 3 ms 192760 KB Output is correct
26 Correct 3 ms 192760 KB Output is correct
27 Correct 83 ms 192760 KB Output is correct
28 Correct 5 ms 192760 KB Output is correct
29 Correct 4575 ms 192760 KB Output is correct
30 Correct 13981 ms 195532 KB Output is correct
31 Execution timed out 20082 ms 203768 KB Time limit exceeded
32 Halted 0 ms 0 KB -