oj.uz

Submission #1067803

# Submission time Handle Problem Language Result Execution time Memory
1067803 2024-08-21T03:30:55 Z sleepntsheep Wombats (IOI13_wombats) C++17
39 / 100
 3052 ms 26104 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) {
		for (int i = 0; i + 1 < r; ++i) for (int j = 0; j < c; ++j)
			changeV(i, j, V[i][j]);
		for (int i = 0 ; i < r; ++i) for (int j = 0; j + 1 < c; ++j)
			changeH(i, j, H[i][j]);
	}
}

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(dp[0][V1] = 0, 0, V1);
		while (hp.size()) {
			auto [cst, y, x] = *hp.begin();
			hp.erase(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 4184 KB Output is correct
2 Correct 3 ms 4188 KB Output is correct
3 Correct 42 ms 5904 KB Output is correct
4 Correct 3 ms 4184 KB Output is correct
5 Correct 3 ms 4188 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 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 174 ms 860 KB Output is correct
5 Correct 168 ms 856 KB Output is correct
6 Correct 172 ms 860 KB Output is correct
7 Correct 168 ms 856 KB Output is correct
8 Correct 126 ms 1076 KB Output is correct
9 Correct 143 ms 860 KB Output is correct
10 Correct 143 ms 860 KB Output is correct
11 Correct 216 ms 1848 KB Output is correct
12 Correct 166 ms 856 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 600 KB Output is correct
2 Correct 179 ms 856 KB Output is correct
3 Correct 154 ms 860 KB Output is correct
4 Correct 155 ms 884 KB Output is correct
5 Correct 149 ms 856 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 165 ms 892 KB Output is correct
10 Incorrect 1 ms 1112 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15960 KB Output is correct
2 Correct 37 ms 15996 KB Output is correct
3 Correct 37 ms 15960 KB Output is correct
4 Correct 2980 ms 16860 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 604 KB Output is correct
2 Correct 178 ms 860 KB Output is correct
3 Correct 155 ms 860 KB Output is correct
4 Correct 152 ms 856 KB Output is correct
5 Correct 151 ms 860 KB Output is correct
6 Correct 36 ms 15964 KB Output is correct
7 Correct 36 ms 15964 KB Output is correct
8 Correct 36 ms 16032 KB Output is correct
9 Correct 3052 ms 17488 KB Output is correct
10 Correct 2 ms 4188 KB Output is correct
11 Correct 2 ms 4352 KB Output is correct
12 Correct 45 ms 7112 KB Output is correct
13 Correct 2 ms 4188 KB Output is correct
14 Correct 2 ms 4188 KB Output is correct
15 Correct 0 ms 428 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 167 ms 1092 KB Output is correct
19 Correct 171 ms 860 KB Output is correct
20 Correct 167 ms 856 KB Output is correct
21 Correct 167 ms 860 KB Output is correct
22 Correct 122 ms 1080 KB Output is correct
23 Correct 143 ms 1084 KB Output is correct
24 Correct 143 ms 856 KB Output is correct
25 Correct 208 ms 3408 KB Output is correct
26 Correct 167 ms 1084 KB Output is correct
27 Correct 164 ms 860 KB Output is correct
28 Runtime error 66 ms 19796 KB Execution killed with signal 4
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 600 KB Output is correct
2 Correct 182 ms 864 KB Output is correct
3 Correct 151 ms 856 KB Output is correct
4 Correct 152 ms 860 KB Output is correct
5 Correct 157 ms 860 KB Output is correct
6 Correct 35 ms 15964 KB Output is correct
7 Correct 36 ms 15960 KB Output is correct
8 Correct 36 ms 15964 KB Output is correct
9 Correct 2979 ms 17492 KB Output is correct
10 Correct 2 ms 4188 KB Output is correct
11 Correct 2 ms 4188 KB Output is correct
12 Correct 40 ms 6996 KB Output is correct
13 Correct 2 ms 4188 KB Output is correct
14 Correct 2 ms 4188 KB Output is correct
15 Runtime error 133 ms 26104 KB Execution killed with signal 4
16 Halted 0 ms 0 KB -