oj.uz

Submission #591168

# Submission time Handle Problem Language Result Execution time Memory
591168 2022-07-06T23:57:24 Z Temmie Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 247640 KB 
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx2,tune=native")

#include "wombats.h"
#include <bits/stdc++.h>

constexpr const int BS = 7;
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 ine[mxc][mxc];
		memset(con, mxv, sizeof(con));
		if (ec - sc < c) {
			for (int j = 0; j < c; j++) {
				for (int k = 0; k < c; k++) {
					con[j][k] = std::min(con[j][k], lower->con[j][k] + v[upper->ec][j]);
				}
				if (j) {
					for (int k = 0; k < c; k++) {
						con[j][k] = std::min(con[j][k], con[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++) {
						con[j][k] = std::min(con[j][k], con[j + 1][k] + h[upper->ec][j]);
					}
				}
			}
			for (int i = upper->ec - 1; i >= sc; i--) {
				memset(ine, mxv, sizeof(ine));
				for (int j = 0; j < c; j++) {
					if (i != ec) {
						for (int k = 0; k < c; k++) {
							ine[j][k] = std::min(ine[j][k], con[j][k] + v[i][j]);
						}
					}
					if (j) {
						for (int k = 0; k < c; k++) {
							ine[j][k] = std::min(ine[j][k], ine[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++) {
							ine[j][k] = std::min(ine[j][k], ine[j + 1][k] + h[i][j]);
						}
					}
				}
				memcpy(con, ine, sizeof(ine));
			}
			return;
		}
		memset(ine, mxv, sizeof(ine));
		{
			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++) {
					con[i][k] = std::min(con[i][k], upper->con[i][j] + ine[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 261 ms 242244 KB Output is correct
2 Correct 255 ms 242252 KB Output is correct
3 Correct 311 ms 243788 KB Output is correct
4 Correct 259 ms 242260 KB Output is correct
5 Correct 273 ms 242256 KB Output is correct
6 Correct 5 ms 8404 KB Output is correct
7 Correct 4 ms 8404 KB Output is correct
8 Correct 4 ms 8404 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 5 ms 9428 KB Output is correct
5 Correct 5 ms 9428 KB Output is correct
6 Correct 5 ms 9428 KB Output is correct
7 Correct 6 ms 9428 KB Output is correct
8 Correct 7 ms 9428 KB Output is correct
9 Correct 6 ms 9428 KB Output is correct
10 Correct 8 ms 9428 KB Output is correct
11 Correct 67 ms 10360 KB Output is correct
12 Correct 6 ms 9428 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 13424 KB Output is correct
2 Correct 443 ms 13428 KB Output is correct
3 Correct 492 ms 13464 KB Output is correct
4 Correct 471 ms 13428 KB Output is correct
5 Correct 323 ms 13396 KB Output is correct
6 Correct 4 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 2172 ms 13440 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 246 ms 246164 KB Output is correct
2 Correct 244 ms 246164 KB Output is correct
3 Correct 266 ms 246228 KB Output is correct
4 Correct 305 ms 246880 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 13424 KB Output is correct
2 Correct 465 ms 13440 KB Output is correct
3 Correct 441 ms 13428 KB Output is correct
4 Correct 453 ms 13388 KB Output is correct
5 Correct 321 ms 13460 KB Output is correct
6 Correct 240 ms 246124 KB Output is correct
7 Correct 230 ms 246176 KB Output is correct
8 Correct 293 ms 246144 KB Output is correct
9 Correct 263 ms 246872 KB Output is correct
10 Correct 248 ms 242268 KB Output is correct
11 Correct 227 ms 242260 KB Output is correct
12 Correct 302 ms 243804 KB Output is correct
13 Correct 251 ms 242252 KB Output is correct
14 Correct 234 ms 242164 KB Output is correct
15 Correct 5 ms 8404 KB Output is correct
16 Correct 5 ms 8404 KB Output is correct
17 Correct 5 ms 8404 KB Output is correct
18 Correct 6 ms 9428 KB Output is correct
19 Correct 6 ms 9388 KB Output is correct
20 Correct 7 ms 9428 KB Output is correct
21 Correct 7 ms 9428 KB Output is correct
22 Correct 6 ms 9428 KB Output is correct
23 Correct 5 ms 9372 KB Output is correct
24 Correct 5 ms 9428 KB Output is correct
25 Correct 73 ms 10348 KB Output is correct
26 Correct 5 ms 9428 KB Output is correct
27 Correct 2146 ms 13420 KB Output is correct
28 Correct 4685 ms 246616 KB Output is correct
29 Correct 4993 ms 203764 KB Output is correct
30 Correct 4494 ms 203904 KB Output is correct
31 Correct 5326 ms 247520 KB Output is correct
32 Correct 6 ms 8404 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 13420 KB Output is correct
2 Correct 473 ms 13428 KB Output is correct
3 Correct 455 ms 13420 KB Output is correct
4 Correct 465 ms 13428 KB Output is correct
5 Correct 360 ms 13436 KB Output is correct
6 Correct 243 ms 246284 KB Output is correct
7 Correct 240 ms 246092 KB Output is correct
8 Correct 251 ms 246164 KB Output is correct
9 Correct 275 ms 246972 KB Output is correct
10 Correct 224 ms 242172 KB Output is correct
11 Correct 265 ms 242352 KB Output is correct
12 Correct 333 ms 243864 KB Output is correct
13 Correct 240 ms 242264 KB Output is correct
14 Correct 252 ms 242324 KB Output is correct
15 Correct 2552 ms 246252 KB Output is correct
16 Execution timed out 20048 ms 247640 KB Time limit exceeded
17 Halted 0 ms 0 KB -