oj.uz

Submission #591164

# Submission time Handle Problem Language Result Execution time Memory
591164 2022-07-06T23:49:29 Z Temmie Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 248084 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 240 ms 242164 KB Output is correct
2 Correct 258 ms 242148 KB Output is correct
3 Correct 321 ms 243788 KB Output is correct
4 Correct 255 ms 242380 KB Output is correct
5 Correct 237 ms 242268 KB Output is correct
6 Correct 4 ms 8404 KB Output is correct
7 Correct 5 ms 8464 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 6 ms 8364 KB Output is correct
2 Correct 4 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 6 ms 9400 KB Output is correct
6 Correct 5 ms 9428 KB Output is correct
7 Correct 6 ms 9368 KB Output is correct
8 Correct 5 ms 9400 KB Output is correct
9 Correct 6 ms 9360 KB Output is correct
10 Correct 6 ms 9400 KB Output is correct
11 Correct 73 ms 10872 KB Output is correct
12 Correct 6 ms 9444 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 13420 KB Output is correct
2 Correct 423 ms 13496 KB Output is correct
3 Correct 449 ms 13504 KB Output is correct
4 Correct 466 ms 13508 KB Output is correct
5 Correct 418 ms 13388 KB Output is correct
6 Correct 4 ms 8404 KB Output is correct
7 Correct 6 ms 8404 KB Output is correct
8 Correct 6 ms 8416 KB Output is correct
9 Correct 2119 ms 13496 KB Output is correct
10 Correct 4 ms 8376 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 246172 KB Output is correct
2 Correct 252 ms 246168 KB Output is correct
3 Correct 272 ms 246104 KB Output is correct
4 Correct 267 ms 246860 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 13424 KB Output is correct
2 Correct 443 ms 13492 KB Output is correct
3 Correct 430 ms 13504 KB Output is correct
4 Correct 437 ms 13508 KB Output is correct
5 Correct 447 ms 13508 KB Output is correct
6 Correct 227 ms 246148 KB Output is correct
7 Correct 232 ms 246208 KB Output is correct
8 Correct 280 ms 246172 KB Output is correct
9 Correct 259 ms 247424 KB Output is correct
10 Correct 296 ms 242236 KB Output is correct
11 Correct 240 ms 242292 KB Output is correct
12 Correct 308 ms 244324 KB Output is correct
13 Correct 243 ms 242252 KB Output is correct
14 Correct 256 ms 242292 KB Output is correct
15 Correct 5 ms 8404 KB Output is correct
16 Correct 6 ms 8404 KB Output is correct
17 Correct 5 ms 8404 KB Output is correct
18 Correct 5 ms 9428 KB Output is correct
19 Correct 6 ms 9428 KB Output is correct
20 Correct 5 ms 9428 KB Output is correct
21 Correct 6 ms 9428 KB Output is correct
22 Correct 5 ms 9428 KB Output is correct
23 Correct 6 ms 9428 KB Output is correct
24 Correct 6 ms 9428 KB Output is correct
25 Correct 70 ms 10944 KB Output is correct
26 Correct 5 ms 9404 KB Output is correct
27 Correct 2192 ms 13508 KB Output is correct
28 Correct 5538 ms 246916 KB Output is correct
29 Correct 5806 ms 204220 KB Output is correct
30 Correct 5173 ms 204432 KB Output is correct
31 Correct 5941 ms 248012 KB Output is correct
32 Correct 5 ms 8404 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 13420 KB Output is correct
2 Correct 427 ms 13492 KB Output is correct
3 Correct 444 ms 13504 KB Output is correct
4 Correct 423 ms 13516 KB Output is correct
5 Correct 425 ms 13508 KB Output is correct
6 Correct 232 ms 246172 KB Output is correct
7 Correct 261 ms 246152 KB Output is correct
8 Correct 250 ms 246248 KB Output is correct
9 Correct 300 ms 247484 KB Output is correct
10 Correct 284 ms 242284 KB Output is correct
11 Correct 226 ms 242484 KB Output is correct
12 Correct 308 ms 244364 KB Output is correct
13 Correct 238 ms 242176 KB Output is correct
14 Correct 232 ms 242252 KB Output is correct
15 Correct 6013 ms 247528 KB Output is correct
16 Execution timed out 20057 ms 248084 KB Time limit exceeded
17 Halted 0 ms 0 KB -