oj.uz

Submission #591578

# Submission time Handle Problem Language Result Execution time Memory
591578 2022-07-07T15:52:11 Z Temmie Wombats (IOI13_wombats) C++17
100 / 100
 9235 ms 65528 KB 
#include "wombats.h"
#include <bits/stdc++.h>

constexpr const int BS = 40;
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;
		for (int i = 0; i < c; i++) {
			con[i][i] = 0;
			for (int j = sc; j <= ec; j++) {
				for (int k = 1; k < c; k++) {
					con[i][k] = std::min(con[i][k], con[i][k - 1] + h[j][k - 1]);
				}
				for (int k = c - 2; k >= 0; k--) {
					con[i][k] = std::min(con[i][k], con[i][k + 1] + h[j][k]);
				}
				for (int k = 0; k < c; k++) {
					con[i][k] += j + 1 == r ? 0 : v[j][k];
				}
			}
		}
	}
	
	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;
		}
		static unsigned int bes[mxc][mxc];
		for (int d = -c - 1; d < c; d++) {
			for (int i = std::max(0, -d); i + std::max(0, d) < c; i++) {
				int j = i + d;
				int l = 0;
				int r = c - 1;
				if (j) {
					l = bes[i][j - 1];
				}
				if (i + 1 < c) {
					r = bes[i + 1][j];
				}
				con[i][j] = 1 << 30;
				for (int k = l; k <= r; k++) {
					if (upper->con[i][k] + lower->con[k][j] < con[i][j]) {
						con[i][j] = upper->con[i][k] + lower->con[k][j];
						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();
				memset(v[now]->con, mxv, sizeof(v[now]->con));
				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 22 ms 52256 KB Output is correct
2 Correct 22 ms 52308 KB Output is correct
3 Correct 84 ms 53872 KB Output is correct
4 Correct 23 ms 52224 KB Output is correct
5 Correct 22 ms 52316 KB Output is correct
6 Correct 4 ms 8276 KB Output is correct
7 Correct 4 ms 8276 KB Output is correct
8 Correct 5 ms 8280 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8212 KB Output is correct
2 Correct 4 ms 8276 KB Output is correct
3 Correct 6 ms 8212 KB Output is correct
4 Correct 5 ms 8276 KB Output is correct
5 Correct 6 ms 8324 KB Output is correct
6 Correct 5 ms 8276 KB Output is correct
7 Correct 5 ms 8276 KB Output is correct
8 Correct 5 ms 8276 KB Output is correct
9 Correct 6 ms 8276 KB Output is correct
10 Correct 5 ms 8244 KB Output is correct
11 Correct 68 ms 9320 KB Output is correct
12 Correct 5 ms 8248 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 9348 KB Output is correct
2 Correct 341 ms 9252 KB Output is correct
3 Correct 340 ms 9364 KB Output is correct
4 Correct 310 ms 9348 KB Output is correct
5 Correct 370 ms 9420 KB Output is correct
6 Correct 4 ms 8276 KB Output is correct
7 Correct 4 ms 8276 KB Output is correct
8 Correct 4 ms 8276 KB Output is correct
9 Correct 1676 ms 9356 KB Output is correct
10 Correct 4 ms 8276 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 56188 KB Output is correct
2 Correct 27 ms 56148 KB Output is correct
3 Correct 26 ms 56188 KB Output is correct
4 Correct 58 ms 56972 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 9300 KB Output is correct
2 Correct 355 ms 9404 KB Output is correct
3 Correct 315 ms 9428 KB Output is correct
4 Correct 330 ms 9364 KB Output is correct
5 Correct 351 ms 9348 KB Output is correct
6 Correct 32 ms 56148 KB Output is correct
7 Correct 25 ms 56148 KB Output is correct
8 Correct 26 ms 56220 KB Output is correct
9 Correct 56 ms 56904 KB Output is correct
10 Correct 21 ms 52292 KB Output is correct
11 Correct 22 ms 52300 KB Output is correct
12 Correct 84 ms 53860 KB Output is correct
13 Correct 22 ms 52300 KB Output is correct
14 Correct 22 ms 52308 KB Output is correct
15 Correct 4 ms 8276 KB Output is correct
16 Correct 6 ms 8276 KB Output is correct
17 Correct 4 ms 8276 KB Output is correct
18 Correct 4 ms 8276 KB Output is correct
19 Correct 5 ms 8276 KB Output is correct
20 Correct 4 ms 8276 KB Output is correct
21 Correct 4 ms 8276 KB Output is correct
22 Correct 4 ms 8276 KB Output is correct
23 Correct 5 ms 8276 KB Output is correct
24 Correct 4 ms 8300 KB Output is correct
25 Correct 66 ms 9292 KB Output is correct
26 Correct 5 ms 8276 KB Output is correct
27 Correct 1679 ms 9356 KB Output is correct
28 Correct 2295 ms 56764 KB Output is correct
29 Correct 2281 ms 48524 KB Output is correct
30 Correct 2221 ms 48520 KB Output is correct
31 Correct 2385 ms 57852 KB Output is correct
32 Correct 4 ms 8276 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 9348 KB Output is correct
2 Correct 345 ms 9364 KB Output is correct
3 Correct 311 ms 9348 KB Output is correct
4 Correct 309 ms 9368 KB Output is correct
5 Correct 351 ms 9420 KB Output is correct
6 Correct 24 ms 56124 KB Output is correct
7 Correct 23 ms 56148 KB Output is correct
8 Correct 24 ms 56168 KB Output is correct
9 Correct 55 ms 56888 KB Output is correct
10 Correct 22 ms 52232 KB Output is correct
11 Correct 23 ms 52216 KB Output is correct
12 Correct 90 ms 53848 KB Output is correct
13 Correct 22 ms 52308 KB Output is correct
14 Correct 22 ms 52240 KB Output is correct
15 Correct 1785 ms 56264 KB Output is correct
16 Correct 9235 ms 58272 KB Output is correct
17 Correct 5 ms 8276 KB Output is correct
18 Correct 5 ms 8276 KB Output is correct
19 Correct 5 ms 8252 KB Output is correct
20 Correct 4 ms 8276 KB Output is correct
21 Correct 4 ms 8276 KB Output is correct
22 Correct 5 ms 8260 KB Output is correct
23 Correct 5 ms 8276 KB Output is correct
24 Correct 5 ms 8276 KB Output is correct
25 Correct 5 ms 8276 KB Output is correct
26 Correct 5 ms 8260 KB Output is correct
27 Correct 70 ms 10604 KB Output is correct
28 Correct 4 ms 8276 KB Output is correct
29 Correct 1617 ms 9428 KB Output is correct
30 Correct 2233 ms 60460 KB Output is correct
31 Correct 8629 ms 64700 KB Output is correct
32 Correct 8657 ms 64708 KB Output is correct
33 Correct 2181 ms 51968 KB Output is correct
34 Correct 8534 ms 55856 KB Output is correct
35 Correct 2159 ms 51904 KB Output is correct
36 Correct 8530 ms 55760 KB Output is correct
37 Correct 2294 ms 62044 KB Output is correct
38 Correct 8755 ms 65528 KB Output is correct
39 Correct 4 ms 8276 KB Output is correct
40 Correct 8834 ms 56028 KB Output is correct