oj.uz

Submission #591165

# Submission time Handle Problem Language Result Execution time Memory
591165 2022-07-06T23:51:04 Z Temmie Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 247692 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(ine, mxv, sizeof(ine));
		memset(con, mxv, sizeof(con));
		{
			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 227 ms 242224 KB Output is correct
2 Correct 231 ms 242268 KB Output is correct
3 Correct 318 ms 243924 KB Output is correct
4 Correct 249 ms 242264 KB Output is correct
5 Correct 270 ms 242232 KB Output is correct
6 Correct 5 ms 8404 KB Output is correct
7 Correct 5 ms 8376 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 4 ms 8404 KB Output is correct
2 Correct 6 ms 8404 KB Output is correct
3 Correct 5 ms 8404 KB Output is correct
4 Correct 6 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 5 ms 9428 KB Output is correct
8 Correct 5 ms 9428 KB Output is correct
9 Correct 5 ms 9428 KB Output is correct
10 Correct 6 ms 9400 KB Output is correct
11 Correct 66 ms 10336 KB Output is correct
12 Correct 5 ms 9472 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 13428 KB Output is correct
2 Correct 418 ms 13420 KB Output is correct
3 Correct 425 ms 13372 KB Output is correct
4 Correct 426 ms 13428 KB Output is correct
5 Correct 410 ms 13384 KB Output is correct
6 Correct 4 ms 8404 KB Output is correct
7 Correct 4 ms 8404 KB Output is correct
8 Correct 4 ms 8404 KB Output is correct
9 Correct 2041 ms 13424 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 256 ms 246116 KB Output is correct
2 Correct 236 ms 246092 KB Output is correct
3 Correct 293 ms 246168 KB Output is correct
4 Correct 273 ms 246852 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 13428 KB Output is correct
2 Correct 421 ms 13424 KB Output is correct
3 Correct 427 ms 13428 KB Output is correct
4 Correct 448 ms 13428 KB Output is correct
5 Correct 447 ms 13436 KB Output is correct
6 Correct 226 ms 246176 KB Output is correct
7 Correct 254 ms 246152 KB Output is correct
8 Correct 246 ms 246168 KB Output is correct
9 Correct 271 ms 246892 KB Output is correct
10 Correct 238 ms 242176 KB Output is correct
11 Correct 231 ms 242264 KB Output is correct
12 Correct 334 ms 243940 KB Output is correct
13 Correct 237 ms 242252 KB Output is correct
14 Correct 234 ms 242264 KB Output is correct
15 Correct 5 ms 8404 KB Output is correct
16 Correct 5 ms 8404 KB Output is correct
17 Correct 6 ms 8404 KB Output is correct
18 Correct 6 ms 9428 KB Output is correct
19 Correct 7 ms 9436 KB Output is correct
20 Correct 5 ms 9428 KB Output is correct
21 Correct 5 ms 9428 KB Output is correct
22 Correct 5 ms 9428 KB Output is correct
23 Correct 5 ms 9428 KB Output is correct
24 Correct 5 ms 9428 KB Output is correct
25 Correct 65 ms 10372 KB Output is correct
26 Correct 8 ms 9428 KB Output is correct
27 Correct 2041 ms 13420 KB Output is correct
28 Correct 5457 ms 246640 KB Output is correct
29 Correct 5772 ms 203952 KB Output is correct
30 Correct 5101 ms 203940 KB Output is correct
31 Correct 5965 ms 247692 KB Output is correct
32 Correct 4 ms 8404 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 13436 KB Output is correct
2 Correct 403 ms 13432 KB Output is correct
3 Correct 475 ms 13424 KB Output is correct
4 Correct 416 ms 13424 KB Output is correct
5 Correct 410 ms 13424 KB Output is correct
6 Correct 236 ms 246124 KB Output is correct
7 Correct 274 ms 246168 KB Output is correct
8 Correct 252 ms 246184 KB Output is correct
9 Correct 272 ms 246944 KB Output is correct
10 Correct 234 ms 242264 KB Output is correct
11 Correct 225 ms 242164 KB Output is correct
12 Correct 302 ms 243776 KB Output is correct
13 Correct 287 ms 242260 KB Output is correct
14 Correct 235 ms 242192 KB Output is correct
15 Correct 6074 ms 246052 KB Output is correct
16 Execution timed out 20065 ms 246856 KB Time limit exceeded
17 Halted 0 ms 0 KB -