oj.uz

Submission #591025

# Submission time Handle Problem Language Result Execution time Memory
591025 2022-07-06T18:25:51 Z Temmie Wombats (IOI13_wombats) C++17
76 / 100
 7845 ms 262144 KB 
#include "wombats.h"
#include <bits/stdc++.h>

constexpr const int BS = 5;

int r, c;
std::vector <std::vector <int>> h, v;

struct Block {
	
	int sc = -1, ec = -1;
	std::vector <std::vector <int>> con;
	
	Block(bool empty = false) :
	con(!empty * c, std::vector <int> (c, 1 << 30))
	{ }
	
	void update(int _sc, int _ec) {
		sc = _sc;
		ec = _ec;
		for (int i = 0; i < c; i++) {
			for (int j = 0; j < c; j++) {
				con[i][j] = 1 << 30;
			}
		}
		for (int j = 0; j < c; j++) {
			con[j][j] = 0;
		}
		for (int i = ec; i >= sc; i--) {
			std::vector <std::vector <int>> nxt(c, std::vector <int> (c, 1 << 30));
			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]);
					}
				}
			}
			std::swap(con, nxt);
		}
	}
	
	friend Block merge(const Block& upper, const Block& lower) {
		if (!upper.con.empty() && lower.con.empty()) {
			return upper;
		}
		if (upper.con.empty()) {
			assert(lower.con.empty());
			return Block(true);
		}
		Block res;
		res.sc = upper.sc;
		res.ec = lower.ec;
		std::vector <std::vector <int>> ine(c, std::vector <int> (c, 1 << 30));
		{
			for (int j = 0; j < c; j++) {
				for (int k = 0; k < c; k++) {
					ine[j][k] = std::min(ine[j][k], lower.con[j][k] + v[upper.ec][j]);
				}
				if (j) {
					for (int k = 0; k < c; k++) {
						ine[j][k] = std::min(ine[j][k], ine[j - 1][k] + h[upper.ec][j - 1]);
					}
				}
			}
			for (int j = c - 1; j >= 0; j--) {
				if (j + 1 < c) {
					for (int k = 0; k < c; k++) {
						ine[j][k] = std::min(ine[j][k], ine[j + 1][k] + h[upper.ec][j]);
					}
				}
			}
		}
		for (int i = 0; i < c; i++) {
			for (int j = 0; j < c; j++) {
				for (int k = 0; k < c; k++) {
					res.con[i][k] = std::min(res.con[i][k], upper.con[i][j] + ine[j][k]);
				}
			}
		}
		return res;
	}
	
};

struct Seg {
	
	int size;
	std::vector <Block> v;
	
	Seg(int s) {
		size = 1;
		while (size < s) {
			size <<= 1;
		}
		v.resize(size << 1, Block(true));
		build(0, 0, size);
	}
	
	void build(int now, int li, int ri) {
		if (!(ri - li - 1)) {
			if (li * BS < r) {
				v[now] = 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);
		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);
		}
		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;
	h.resize(r, std::vector <int> (c - 1));
	v.resize(r - 1, std::vector <int> (c));
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (j < c - 1) {
				h[i][j] = H[i][j];
			}
			if (i < r - 1) {
				v[i][j] = V[i][j];
			}
		}
	}
	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 5 ms 4692 KB Output is correct
2 Correct 6 ms 4820 KB Output is correct
3 Correct 85 ms 7528 KB Output is correct
4 Correct 5 ms 4820 KB Output is correct
5 Correct 4 ms 4820 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 72 ms 1360 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 2412 KB Output is correct
2 Correct 624 ms 2376 KB Output is correct
3 Correct 552 ms 2544 KB Output is correct
4 Correct 564 ms 2420 KB Output is correct
5 Correct 583 ms 2384 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 2896 ms 2532 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8916 KB Output is correct
2 Correct 10 ms 9044 KB Output is correct
3 Correct 9 ms 9024 KB Output is correct
4 Correct 42 ms 10312 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 2412 KB Output is correct
2 Correct 601 ms 2372 KB Output is correct
3 Correct 565 ms 2536 KB Output is correct
4 Correct 521 ms 2424 KB Output is correct
5 Correct 597 ms 2380 KB Output is correct
6 Correct 8 ms 8916 KB Output is correct
7 Correct 9 ms 8992 KB Output is correct
8 Correct 8 ms 9044 KB Output is correct
9 Correct 40 ms 10376 KB Output is correct
10 Correct 4 ms 4820 KB Output is correct
11 Correct 4 ms 4804 KB Output is correct
12 Correct 66 ms 7568 KB Output is correct
13 Correct 5 ms 4820 KB Output is correct
14 Correct 5 ms 4820 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 316 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 69 ms 2724 KB Output is correct
26 Correct 1 ms 316 KB Output is correct
27 Correct 2876 ms 2488 KB Output is correct
28 Correct 7086 ms 103200 KB Output is correct
29 Correct 6703 ms 85240 KB Output is correct
30 Correct 6483 ms 85316 KB Output is correct
31 Correct 7845 ms 104884 KB Output is correct
32 Correct 1 ms 212 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 2404 KB Output is correct
2 Correct 683 ms 2380 KB Output is correct
3 Correct 581 ms 2424 KB Output is correct
4 Correct 610 ms 2412 KB Output is correct
5 Correct 678 ms 2384 KB Output is correct
6 Correct 9 ms 8916 KB Output is correct
7 Correct 9 ms 9048 KB Output is correct
8 Correct 11 ms 8988 KB Output is correct
9 Correct 45 ms 10396 KB Output is correct
10 Correct 5 ms 4764 KB Output is correct
11 Correct 6 ms 4820 KB Output is correct
12 Correct 81 ms 7584 KB Output is correct
13 Correct 6 ms 4804 KB Output is correct
14 Correct 6 ms 4820 KB Output is correct
15 Runtime error 7648 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -