oj.uz

Submission #591537

# Submission time Handle Problem Language Result Execution time Memory
591537 2022-07-07T14:46:03 Z Temmie Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 250140 KB 
#include "wombats.h"
#include <bits/stdc++.h>

constexpr const int BS = 7;
constexpr const int mxr = 5000;
constexpr const int mxc = 200;
constexpr const int mxv = 0b01111111;

int r, c;
unsigned int h[mxr][mxc];
unsigned int v[mxr][mxc];

struct Block {
	
	int sc = -1, ec = -1;
	unsigned int con[mxc][mxc];
	
	void update(int _sc, int _ec) {
		sc = _sc;
		ec = _ec;
		memset(con, mxv, sizeof(con));
		for (int j = 0; j < c; j++) {
			con[j][j] = 0;
		}
		static unsigned int nxt[mxc][mxc];
		for (int i = ec; i >= sc; i--) {
			memset(nxt, mxv, sizeof(nxt));
			if (i == ec) {
				for (int j = 0; j < c; j++) {
					nxt[j][j] = 0;
				}
			}
			for (int j = 0; j < c; j++) {
				if (i != ec) {
					for (int k = 0; k < c; k++) {
						nxt[j][k] = std::min(nxt[j][k], con[j][k] + v[i][j]);
					}
				}
				if (j) {
					for (int k = 0; k < c; k++) {
						nxt[j][k] = std::min(nxt[j][k], nxt[j - 1][k] + h[i][j - 1]);
					}
				}
			}
			for (int j = c - 1; j >= 0; j--) {
				if (j + 1 < c) {
					for (int k = 0; k < c; k++) {
						nxt[j][k] = std::min(nxt[j][k], nxt[j + 1][k] + h[i][j]);
					}
				}
			}
			memcpy(con, nxt, sizeof(nxt));
		}
	}
	
	void merge(const Block* upper, const Block* lower) {
		if (upper && !lower) {
			sc = upper->sc;
			ec = upper->ec;
			memcpy(con, upper->con, sizeof(upper->con));
			return;
		}
		if (!upper) {
			assert(!lower);
			return;
		}
		sc = upper->sc;
		ec = lower->ec;
		static unsigned int bes[mxc][mxc];
		memset(con, mxv, sizeof(con));
		memset(bes, mxv, sizeof(bes));
		for (int d = 0; d <= c; d++) {
			for (int i = 0; i < c; i++) {
				int from = std::max(0, i - d);
				int to = std::min(c - 1, i + d);
				for (int j = from; j <= to; j++) {
					int l = 0, r = c - 1;
					if (i && j && bes[i - 1][j - 1] < 1000) {
						l = bes[i - 1][j - 1];
					}
					if (i + 1 < c && j + 1 < c && bes[i + 1][j + 1] < 1000) {
						r = bes[i + 1][j + 1];
					}
					for (int k = l; k <= r; k++) {
						if (upper->con[i][k] + lower->con[k][j] + v[upper->ec][k] < con[i][j]) {
							con[i][j] = upper->con[i][k] + lower->con[k][j] + v[upper->ec][k];
							bes[i][j] = k;
						}
					}
				} 
			}
		}
	}
	
};

struct Seg {
	
	int size;
	std::vector <Block*> v;
	
	Seg(int s) {
		size = 1;
		while (size < s) {
			size <<= 1;
		}
		v.resize(size << 1, nullptr);
		build(0, 0, size);
	}
	
	void build(int now, int li, int ri) {
		if (!(ri - li - 1)) {
			if (li * BS < r) {
				v[now] = new Block();
				v[now]->update(li * BS, std::min(r - 1, (li + 1) * BS - 1));
			}
			return;
		}
		int mid = (li + ri) >> 1;
		build(now * 2 + 1, li, mid);
		build(now * 2 + 2, mid, ri);
		if (v[now * 2 + 1]) {
			v[now] = new Block();
			v[now]->merge(v[now * 2 + 1], v[now * 2 + 2]);
		}
	}
	
	void update(int ind) {
		update(ind, 0, 0, size);
	}
	
	void update(int ind, int now, int li, int ri) {
		if (!(ri - li - 1)) {
			v[now]->update(ind * BS, std::min(r - 1, (ind + 1) * BS - 1));
			return;
		}
		int mid = (li + ri) >> 1;
		if (ind < mid) {
			update(ind, now * 2 + 1, li, mid);
		} else {
			update(ind, now * 2 + 2, mid, ri);
		}
		if (v[now]) {
			v[now]->merge(v[now * 2 + 1], v[now * 2 + 2]);
		}
	}
	
};

Seg* seg;

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	r = R;
	c = C;
	memcpy(h, H, sizeof(h));
	memcpy(v, V, sizeof(v));
	seg = new Seg((r + BS - 1) / BS);
}

void changeH(int p, int q, int w) {
	h[p][q] = w;
	seg->update(p / BS);
}

void changeV(int p, int q, int w) {
	v[p][q] = w;
	seg->update(p / BS);
}

int escape(int v1, int v2) {
	return seg->v[0]->con[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]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 242284 KB Output is correct
2 Correct 267 ms 242228 KB Output is correct
3 Correct 332 ms 245052 KB Output is correct
4 Correct 274 ms 242264 KB Output is correct
5 Correct 335 ms 242200 KB Output is correct
6 Correct 5 ms 8380 KB Output is correct
7 Correct 5 ms 8404 KB Output is correct
8 Correct 6 ms 8384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8376 KB Output is correct
2 Correct 4 ms 8404 KB Output is correct
3 Correct 6 ms 8372 KB Output is correct
4 Correct 9 ms 9428 KB Output is correct
5 Correct 6 ms 9428 KB Output is correct
6 Correct 7 ms 9360 KB Output is correct
7 Correct 6 ms 9356 KB Output is correct
8 Correct 6 ms 9428 KB Output is correct
9 Correct 6 ms 9428 KB Output is correct
10 Correct 7 ms 9428 KB Output is correct
11 Correct 75 ms 11788 KB Output is correct
12 Correct 6 ms 9404 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2976 ms 13504 KB Output is correct
2 Correct 2163 ms 13488 KB Output is correct
3 Correct 2909 ms 13504 KB Output is correct
4 Correct 2757 ms 13504 KB Output is correct
5 Correct 2608 ms 13500 KB Output is correct
6 Correct 5 ms 8400 KB Output is correct
7 Correct 4 ms 8404 KB Output is correct
8 Correct 5 ms 8376 KB Output is correct
9 Correct 9782 ms 13496 KB Output is correct
10 Correct 5 ms 8404 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 246248 KB Output is correct
2 Correct 235 ms 246224 KB Output is correct
3 Correct 252 ms 246236 KB Output is correct
4 Correct 304 ms 247692 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2786 ms 13508 KB Output is correct
2 Correct 2027 ms 13496 KB Output is correct
3 Correct 2895 ms 13508 KB Output is correct
4 Correct 2762 ms 13504 KB Output is correct
5 Correct 2724 ms 13504 KB Output is correct
6 Correct 238 ms 246124 KB Output is correct
7 Correct 242 ms 246144 KB Output is correct
8 Correct 256 ms 246244 KB Output is correct
9 Correct 292 ms 247540 KB Output is correct
10 Correct 237 ms 242292 KB Output is correct
11 Correct 225 ms 242244 KB Output is correct
12 Correct 305 ms 245144 KB Output is correct
13 Correct 249 ms 242300 KB Output is correct
14 Correct 254 ms 242300 KB Output is correct
15 Correct 6 ms 8372 KB Output is correct
16 Correct 5 ms 8372 KB Output is correct
17 Correct 5 ms 8404 KB Output is correct
18 Correct 5 ms 9428 KB Output is correct
19 Correct 5 ms 9404 KB Output is correct
20 Correct 7 ms 9428 KB Output is correct
21 Correct 6 ms 9428 KB Output is correct
22 Correct 5 ms 9428 KB Output is correct
23 Correct 5 ms 9432 KB Output is correct
24 Correct 6 ms 9456 KB Output is correct
25 Correct 68 ms 11732 KB Output is correct
26 Correct 6 ms 9428 KB Output is correct
27 Correct 9589 ms 13500 KB Output is correct
28 Execution timed out 20088 ms 250140 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2690 ms 13624 KB Output is correct
2 Correct 2015 ms 13492 KB Output is correct
3 Correct 2687 ms 13504 KB Output is correct
4 Correct 2712 ms 13508 KB Output is correct
5 Correct 2667 ms 13516 KB Output is correct
6 Correct 291 ms 246244 KB Output is correct
7 Correct 293 ms 246148 KB Output is correct
8 Correct 393 ms 246216 KB Output is correct
9 Correct 394 ms 247636 KB Output is correct
10 Correct 293 ms 242284 KB Output is correct
11 Correct 262 ms 242276 KB Output is correct
12 Correct 429 ms 244996 KB Output is correct
13 Correct 317 ms 242328 KB Output is correct
14 Correct 277 ms 242260 KB Output is correct
15 Execution timed out 20053 ms 141264 KB Time limit exceeded
16 Halted 0 ms 0 KB -