oj.uz

Submission #1067800

# Submission time Handle Problem Language Result Execution time Memory
1067800 2024-08-21T03:28:24 Z sleepntsheep Wombats (IOI13_wombats) C++17
39 / 100
 20000 ms 16828 KB 
#include "wombats.h"
#include <set>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

template <typename T>
using ve = vector<T>;


int r, c, at[9999], h[5000][200], v[5000][200];
int sum = 0;

int changes = 0;


int c_is_2_dp(int V1, int V2) {
	static int dp[5001][2];
	dp[0][V1] = 0;
	dp[0][!V1] = h[0][0];
	for (int i = 1; i < r; ++i) {
		dp[i][0] = dp[i - 1][0] + v[i - 1][0];
		dp[i][1] = dp[i - 1][1] + v[i - 1][1];
		dp[i][0] = min(dp[i][0], dp[i][1] + h[i][0]);
		dp[i][1] = min(dp[i][1], dp[i][0] + h[i][0]);
	}
	return dp[r - 1][V2];
}

void changeH(int P, int Q, int W) {
	if (c <= 100) {
		h[P][Q] = W;
	}

	++changes;
}

void changeV(int P, int Q, int W) {
	if (c == 1) {
		sum += W - at[P];
		at[P] = W;
	} else if (c <= 100) {
		v[P][Q] = W;
	}

	++changes;
}

static int floyd[401][401];
void init(int R, int C, int H[5000][200], int V[5000][200]) {
	r = R, c = C;

	if (c == 1)
		for (int i = 0; i < r; ++i) changeV(i, 0, V[i][0]);
	else if (c == 2) {
		for (int i = 0; i < r; ++i) {
			if (i + 1 < r)
				changeV(i, 0, V[i][0]), changeV(i, 1, V[i][1]);
			changeH(i, 0, H[i][0]);
		}
	} else if (r <= 20 and c <= 20) {
		auto id = [&](int p, int q) { return p * c + q; };
		memset(floyd, 63, sizeof floyd);
		for (int i = 0; i < r * c; ++i) floyd[i][i] = 0;
		for (int i = 0; i + 1 < r; ++i) for (int j = 0; j < c; ++j) {
			int u = id(i, j), v = id(i + 1, j);
			floyd[u][v] = min(floyd[u][v], V[i][j]);
		}
		for (int i = 0 ; i < r; ++i) for (int j = 0; j + 1 < c; ++j) {
			int u = id(i, j), v = id(i, j + 1);
			floyd[u][v] = min(floyd[u][v], H[i][j]);
			floyd[v][u] = min(floyd[v][u], H[i][j]);
		}
		for (int bruh=3;bruh--;)for(int i=0;i<r*c;++i)for(int j=0;j<r*c;++j)for(int k=0;k<r*c;++k)
			floyd[i][j]=min(floyd[i][j],floyd[i][k]+floyd[k][j]);
	} else if (r <= 100 and c <= 100) {
	}
}

int escapes = 0;
int escape(int V1, int V2) {
	if (c == 1)
		return sum;
	else if (c == 2)
		return c_is_2_dp(V1, V2);
	else if (r <= 20 and c <= 20 and 0 == changes)
		return floyd[V1][c * (r - 1) + V2];
	else if (r <= 100 and c <= 100 and ++escapes <= 100) {
		set<tuple<int, int, int>> hp;
		static int dp[101][101];
		memset(dp, 63, sizeof dp);
		hp.emplace(0, 0, V1);
		while (hp.size()) {
			auto [cst, y, x] = *hp.begin();
			if (y == r - 1 and x == V2)
				return cst;
			auto nq = [&](int ww, int ny, int nx) {
				if (dp[ny][nx] > cst + ww) {
					hp.erase({dp[ny][nx], ny, nx});
					dp[ny][nx] = cst + ww;
					hp.emplace(dp[ny][nx], ny, nx);
				}
			};
			if (x + 1 < c) nq(h[y][x], y, x + 1);
			if (y + 1 < r) nq(v[y][x], y + 1, x);
			if (x) nq(h[y][x - 1], y, x - 1);
		}
	}

	__builtin_trap();

}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 37 ms 5928 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 ms 4384 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 169 ms 1072 KB Output is correct
5 Correct 180 ms 1076 KB Output is correct
6 Correct 170 ms 860 KB Output is correct
7 Correct 170 ms 860 KB Output is correct
8 Correct 135 ms 1080 KB Output is correct
9 Correct 162 ms 860 KB Output is correct
10 Correct 147 ms 856 KB Output is correct
11 Correct 207 ms 1860 KB Output is correct
12 Correct 172 ms 1076 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20037 ms 604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15964 KB Output is correct
2 Correct 40 ms 15964 KB Output is correct
3 Correct 34 ms 15960 KB Output is correct
4 Correct 3031 ms 16828 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20048 ms 604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20056 ms 604 KB Time limit exceeded
2 Halted 0 ms 0 KB -