oj.uz

Submission #591542

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

constexpr const int BS = 20;
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 215 ms 92684 KB Output is correct
2 Correct 238 ms 92684 KB Output is correct
3 Correct 287 ms 94284 KB Output is correct
4 Correct 225 ms 92624 KB Output is correct
5 Correct 227 ms 92680 KB Output is correct
6 Correct 4 ms 8404 KB Output is correct
7 Correct 4 ms 8404 KB Output is correct
8 Correct 5 ms 8404 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8404 KB Output is correct
2 Correct 5 ms 8360 KB Output is correct
3 Correct 6 ms 8404 KB Output is correct
4 Correct 4 ms 8404 KB Output is correct
5 Correct 6 ms 8404 KB Output is correct
6 Correct 6 ms 8516 KB Output is correct
7 Correct 5 ms 8404 KB Output is correct
8 Correct 6 ms 8404 KB Output is correct
9 Correct 6 ms 8404 KB Output is correct
10 Correct 5 ms 8404 KB Output is correct
11 Correct 73 ms 9500 KB Output is correct
12 Correct 5 ms 8404 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1321 ms 10380 KB Output is correct
2 Correct 1815 ms 10376 KB Output is correct
3 Correct 2076 ms 10380 KB Output is correct
4 Correct 2931 ms 10380 KB Output is correct
5 Correct 2161 ms 10380 KB Output is correct
6 Correct 6 ms 8404 KB Output is correct
7 Correct 6 ms 8404 KB Output is correct
8 Correct 5 ms 8404 KB Output is correct
9 Correct 9261 ms 10384 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 225 ms 96588 KB Output is correct
2 Correct 256 ms 96772 KB Output is correct
3 Correct 330 ms 96588 KB Output is correct
4 Correct 266 ms 97268 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1206 ms 10504 KB Output is correct
2 Correct 1566 ms 10384 KB Output is correct
3 Correct 1805 ms 10444 KB Output is correct
4 Correct 1833 ms 10388 KB Output is correct
5 Correct 2025 ms 10372 KB Output is correct
6 Correct 219 ms 96588 KB Output is correct
7 Correct 216 ms 96516 KB Output is correct
8 Correct 235 ms 96488 KB Output is correct
9 Correct 245 ms 97312 KB Output is correct
10 Correct 215 ms 92616 KB Output is correct
11 Correct 217 ms 92752 KB Output is correct
12 Correct 276 ms 94212 KB Output is correct
13 Correct 226 ms 92640 KB Output is correct
14 Correct 215 ms 92812 KB Output is correct
15 Correct 4 ms 8404 KB Output is correct
16 Correct 5 ms 8404 KB Output is correct
17 Correct 4 ms 8404 KB Output is correct
18 Correct 5 ms 8508 KB Output is correct
19 Correct 5 ms 8404 KB Output is correct
20 Correct 5 ms 8404 KB Output is correct
21 Correct 4 ms 8404 KB Output is correct
22 Correct 5 ms 8492 KB Output is correct
23 Correct 5 ms 8404 KB Output is correct
24 Correct 5 ms 8404 KB Output is correct
25 Correct 68 ms 9480 KB Output is correct
26 Correct 4 ms 8404 KB Output is correct
27 Correct 7589 ms 10376 KB Output is correct
28 Execution timed out 20066 ms 96840 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1226 ms 10380 KB Output is correct
2 Correct 1553 ms 10380 KB Output is correct
3 Correct 1813 ms 10372 KB Output is correct
4 Correct 1858 ms 10384 KB Output is correct
5 Correct 2053 ms 10376 KB Output is correct
6 Correct 222 ms 96504 KB Output is correct
7 Correct 223 ms 96688 KB Output is correct
8 Correct 227 ms 96592 KB Output is correct
9 Correct 255 ms 97348 KB Output is correct
10 Correct 239 ms 92684 KB Output is correct
11 Correct 215 ms 92672 KB Output is correct
12 Correct 286 ms 94284 KB Output is correct
13 Correct 229 ms 92680 KB Output is correct
14 Correct 238 ms 92680 KB Output is correct
15 Correct 12244 ms 96468 KB Output is correct
16 Execution timed out 20027 ms 96732 KB Time limit exceeded
17 Halted 0 ms 0 KB -