oj.uz

Submission #591575

# Submission time Handle Problem Language Result Execution time Memory
591575 2022-07-07T15:47:25 Z Temmie Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 76212 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 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;
		}
		sc = upper->sc;
		ec = lower->ec;
		assert(upper->ec + 1 < r);
		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 && bes[i][j - 1] < 1000) {
					l = bes[i][j - 1];
				}
				if (i + 1 < c && con[i + 1][j] < 1000) {
					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();
				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 33 ms 66004 KB Output is correct
2 Correct 33 ms 66004 KB Output is correct
3 Correct 103 ms 68160 KB Output is correct
4 Correct 33 ms 66116 KB Output is correct
5 Correct 30 ms 66084 KB Output is correct
6 Correct 5 ms 8276 KB Output is correct
7 Correct 4 ms 8276 KB Output is correct
8 Correct 4 ms 8276 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8276 KB Output is correct
2 Correct 5 ms 8276 KB Output is correct
3 Correct 5 ms 8276 KB Output is correct
4 Correct 4 ms 8276 KB Output is correct
5 Correct 5 ms 8276 KB Output is correct
6 Correct 5 ms 8276 KB Output is correct
7 Correct 6 ms 8276 KB Output is correct
8 Correct 6 ms 8276 KB Output is correct
9 Correct 5 ms 8340 KB Output is correct
10 Correct 5 ms 8316 KB Output is correct
11 Correct 75 ms 9312 KB Output is correct
12 Correct 4 ms 8276 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 9508 KB Output is correct
2 Correct 356 ms 9572 KB Output is correct
3 Correct 331 ms 9508 KB Output is correct
4 Correct 363 ms 9724 KB Output is correct
5 Correct 348 ms 9592 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 8276 KB Output is correct
9 Correct 1794 ms 9588 KB Output is correct
10 Correct 5 ms 8276 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 70004 KB Output is correct
2 Correct 34 ms 70044 KB Output is correct
3 Correct 44 ms 70060 KB Output is correct
4 Correct 66 ms 71396 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 9504 KB Output is correct
2 Correct 346 ms 9644 KB Output is correct
3 Correct 345 ms 9588 KB Output is correct
4 Correct 345 ms 9720 KB Output is correct
5 Correct 368 ms 9556 KB Output is correct
6 Correct 36 ms 69992 KB Output is correct
7 Correct 34 ms 69964 KB Output is correct
8 Correct 37 ms 69936 KB Output is correct
9 Correct 72 ms 71408 KB Output is correct
10 Correct 34 ms 66064 KB Output is correct
11 Correct 35 ms 66004 KB Output is correct
12 Correct 100 ms 68760 KB Output is correct
13 Correct 34 ms 66048 KB Output is correct
14 Correct 33 ms 65996 KB Output is correct
15 Correct 5 ms 8276 KB Output is correct
16 Correct 4 ms 8276 KB Output is correct
17 Correct 5 ms 8252 KB Output is correct
18 Correct 5 ms 8276 KB Output is correct
19 Correct 5 ms 8276 KB Output is correct
20 Correct 7 ms 8276 KB Output is correct
21 Correct 5 ms 8248 KB Output is correct
22 Correct 5 ms 8260 KB Output is correct
23 Correct 6 ms 8276 KB Output is correct
24 Correct 5 ms 8276 KB Output is correct
25 Correct 68 ms 10436 KB Output is correct
26 Correct 6 ms 8276 KB Output is correct
27 Correct 1756 ms 9588 KB Output is correct
28 Correct 3592 ms 71524 KB Output is correct
29 Correct 3921 ms 61044 KB Output is correct
30 Correct 3515 ms 63204 KB Output is correct
31 Correct 3713 ms 76212 KB Output is correct
32 Correct 5 ms 8276 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 9512 KB Output is correct
2 Correct 331 ms 9592 KB Output is correct
3 Correct 338 ms 9596 KB Output is correct
4 Correct 340 ms 9556 KB Output is correct
5 Correct 353 ms 9584 KB Output is correct
6 Correct 36 ms 69964 KB Output is correct
7 Correct 32 ms 70012 KB Output is correct
8 Correct 37 ms 70060 KB Output is correct
9 Correct 65 ms 71464 KB Output is correct
10 Correct 30 ms 66004 KB Output is correct
11 Correct 35 ms 66096 KB Output is correct
12 Correct 96 ms 68680 KB Output is correct
13 Correct 36 ms 66116 KB Output is correct
14 Correct 29 ms 65996 KB Output is correct
15 Correct 2638 ms 72172 KB Output is correct
16 Execution timed out 20056 ms 74928 KB Time limit exceeded
17 Halted 0 ms 0 KB -