oj.uz

Submission #591539

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

constexpr const int BS = 30;
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 313 ms 66364 KB Output is correct
2 Correct 290 ms 66384 KB Output is correct
3 Correct 362 ms 68008 KB Output is correct
4 Correct 315 ms 66424 KB Output is correct
5 Correct 279 ms 66412 KB Output is correct
6 Correct 7 ms 8404 KB Output is correct
7 Correct 5 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 6 ms 8404 KB Output is correct
2 Correct 5 ms 8404 KB Output is correct
3 Correct 4 ms 8404 KB Output is correct
4 Correct 7 ms 8404 KB Output is correct
5 Correct 7 ms 8404 KB Output is correct
6 Correct 6 ms 8516 KB Output is correct
7 Correct 7 ms 8404 KB Output is correct
8 Correct 7 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 9576 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 1439 ms 9940 KB Output is correct
2 Correct 1087 ms 9932 KB Output is correct
3 Correct 1384 ms 9940 KB Output is correct
4 Correct 1415 ms 9816 KB Output is correct
5 Correct 1319 ms 9824 KB Output is correct
6 Correct 5 ms 8404 KB Output is correct
7 Correct 5 ms 8404 KB Output is correct
8 Correct 5 ms 8404 KB Output is correct
9 Correct 10493 ms 9812 KB Output is correct
10 Correct 6 ms 8404 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 70372 KB Output is correct
2 Correct 253 ms 70348 KB Output is correct
3 Correct 276 ms 70476 KB Output is correct
4 Correct 298 ms 71136 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1378 ms 9820 KB Output is correct
2 Correct 1054 ms 9812 KB Output is correct
3 Correct 1333 ms 9820 KB Output is correct
4 Correct 1350 ms 9828 KB Output is correct
5 Correct 1298 ms 9820 KB Output is correct
6 Correct 243 ms 70312 KB Output is correct
7 Correct 245 ms 70344 KB Output is correct
8 Correct 261 ms 70352 KB Output is correct
9 Correct 280 ms 71152 KB Output is correct
10 Correct 248 ms 66380 KB Output is correct
11 Correct 254 ms 66436 KB Output is correct
12 Correct 324 ms 68020 KB Output is correct
13 Correct 262 ms 66388 KB Output is correct
14 Correct 241 ms 66380 KB Output is correct
15 Correct 4 ms 8404 KB Output is correct
16 Correct 5 ms 8472 KB Output is correct
17 Correct 4 ms 8404 KB Output is correct
18 Correct 6 ms 8448 KB Output is correct
19 Correct 5 ms 8404 KB Output is correct
20 Correct 5 ms 8404 KB Output is correct
21 Correct 5 ms 8404 KB Output is correct
22 Correct 5 ms 8404 KB Output is correct
23 Correct 5 ms 8404 KB Output is correct
24 Correct 5 ms 8500 KB Output is correct
25 Correct 75 ms 9692 KB Output is correct
26 Correct 5 ms 8404 KB Output is correct
27 Correct 5250 ms 9812 KB Output is correct
28 Correct 16597 ms 70708 KB Output is correct
29 Execution timed out 20044 ms 63328 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1365 ms 9812 KB Output is correct
2 Correct 1050 ms 9788 KB Output is correct
3 Correct 1353 ms 9824 KB Output is correct
4 Correct 1337 ms 9812 KB Output is correct
5 Correct 1289 ms 9856 KB Output is correct
6 Correct 245 ms 70372 KB Output is correct
7 Correct 251 ms 70464 KB Output is correct
8 Correct 286 ms 70276 KB Output is correct
9 Correct 352 ms 71072 KB Output is correct
10 Correct 284 ms 66432 KB Output is correct
11 Correct 289 ms 66388 KB Output is correct
12 Correct 349 ms 68028 KB Output is correct
13 Correct 312 ms 66260 KB Output is correct
14 Correct 273 ms 66384 KB Output is correct
15 Correct 9141 ms 70288 KB Output is correct
16 Execution timed out 20010 ms 77316 KB Time limit exceeded
17 Halted 0 ms 0 KB -