oj.uz

Submission #1067801

# Submission time Handle Problem Language Result Execution time Memory
1067801 2024-08-21T03:29:44 Z sleepntsheep Wombats (IOI13_wombats) C++17
39 / 100
 2936 ms 16768 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(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 2 ms 4188 KB Output is correct
3 Correct 41 ms 5960 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 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 175 ms 1108 KB Output is correct
5 Correct 167 ms 1076 KB Output is correct
6 Correct 181 ms 860 KB Output is correct
7 Correct 166 ms 860 KB Output is correct
8 Correct 123 ms 1072 KB Output is correct
9 Correct 145 ms 1076 KB Output is correct
10 Correct 144 ms 1076 KB Output is correct
11 Correct 207 ms 1876 KB Output is correct
12 Correct 167 ms 856 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 16216 KB Output is correct
2 Correct 36 ms 15960 KB Output is correct
3 Correct 39 ms 16108 KB Output is correct
4 Correct 2936 ms 16768 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -