oj.uz

Submission #765144

# Submission time Handle Problem Language Result Execution time Memory
765144 2023-06-24T08:44:10 Z Sohsoh84 Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 215156 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pll;

#define X		first
#define Y		second
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const ll MAXN = 5000 + 10;
const ll MAXM = 100 + 10;
const ll INF = 1e9 + 10;
const ll LIM = 3;

int n, m, H[MAXN][MAXM], V[MAXN][MAXM], ps[MAXN][MAXM], sg[MAXN][MAXM][MAXM], opt[MAXM][MAXM], 
    lc[MAXN << 1], rc[MAXN << 1], sgsz = 1, dist[MAXN][MAXM];

inline void update_ps(int i) {
	for (int j = 2; j <= m; j++)
		ps[i][j] = ps[i][j - 1] + H[i][j - 1];
}

inline void update_ans(int mid, int v) {
	for (int x = 1; x <= m; x++) {
		for (int y = 1; y <= m; y++) {
			sg[v][x][y] = sg[lc[v]][x][x] + V[mid][x] + sg[rc[v]][x][y];
			for (int f = 1; f <= m; f++) {
				sg[v][x][y] = min(sg[v][x][y], sg[lc[v]][x][f] + V[mid][f] + sg[rc[v]][f][y]);
			}
		}
	}
}

inline void dijkstra(int x, int y, int r) {
	priority_queue<pair<ll, pll>, vector<pair<ll, pll>>, greater<pair<ll, pll>>> pq;
	for (int i = x; i <= r; i++)
		for (int j = 1; j <= m; j++)
			dist[i][j] = INF;

	dist[x][y] = 0;
	pq.push({dist[x][y], {x, y}});
	
	while (!pq.empty()) {
		auto [d, pos] = pq.top();
		pq.pop();
		auto [x, y] = pos;
		if (dist[x][y] != d) continue;

		if (x < r && dist[x + 1][y] > dist[x][y] + V[x][y]) {
			dist[x + 1][y] = dist[x][y] + V[x][y];
			pq.push({dist[x + 1][y], {x + 1, y}});
		}

		if (y > 1 && dist[x][y - 1] > dist[x][y] + H[x][y - 1]) {
			dist[x][y - 1] = dist[x][y] + H[x][y - 1];
			pq.push({dist[x][y - 1], {x, y - 1}});
		}

		if (y < m && dist[x][y + 1] > dist[x][y] + H[x][y]) {
			dist[x][y + 1] = dist[x][y] + H[x][y];
			pq.push({dist[x][y + 1], {x, y + 1}});
		}
	}
}

inline void tof(int l, int r, int v) {
	for (int i = 1; i <= m; i++) {
		dijkstra(l, i, r);
		for (int j = 1; j <= m; j++)
			sg[v][i][j] = dist[r][j];
	}
}

void build(int l = 1, int r = n, int v = 1) {
	if (r - l + 1 <= LIM) {
		tof(l, r, v);
	} else {
		int mid = (l + r) >> 1;
		lc[v] = ++sgsz;
		rc[v] = ++sgsz;
		build(l, mid, lc[v]);
		build(mid + 1, r, rc[v]);
		update_ans(mid, v);
	}
}

void update(int ind, int l = 1, int r = n, int v = 1) {
	if (r - l + 1 <= LIM) {
		tof(l, r, v);
	} else {
		int mid = (l + r) >> 1;
		if (ind <= mid) update(ind, l, mid, lc[v]);
		else update(ind, mid + 1, r, rc[v]);
		
		update_ans(mid, v);
	}
}

void init(int R_, int C_, int H_[5000][200], int V_[5000][200]) {
	n = R_, m = C_;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j < m; j++)
			H[i][j] = H_[i - 1][j - 1];
	
	for (int i = 1; i < n; i++)
		for (int j = 1; j <= m; j++)
			V[i][j] = V_[i - 1][j - 1];

	for (int i = 1; i <= n; i++)
		update_ps(i);
	
	build();
}

void changeH(int P, int Q, int W) {
	P++, Q++;
	H[P][Q] = W;
	update_ps(P);
	update(P);
}

void changeV(int P, int Q, int W) {
	P++, Q++;
	V[P][Q] = W;
	update(P);
}

int escape(int V1, int V2) {
	V1++, V2++;
	return sg[1][V1][V2];
}

// TODO: 1-base
// TODO: check fit in ll
// TODO: change max limits
// TODO: check n == 1
// TODO: check bounds(n / m)

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 10 ms 25300 KB Output is correct
2 Correct 9 ms 25300 KB Output is correct
3 Correct 63 ms 26848 KB Output is correct
4 Correct 9 ms 25300 KB Output is correct
5 Correct 9 ms 25300 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 55 ms 1596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 728 ms 3920 KB Output is correct
2 Correct 866 ms 3900 KB Output is correct
3 Correct 741 ms 4020 KB Output is correct
4 Correct 753 ms 4016 KB Output is correct
5 Correct 736 ms 3988 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 4124 ms 4028 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 35332 KB Output is correct
2 Correct 14 ms 35308 KB Output is correct
3 Correct 15 ms 35256 KB Output is correct
4 Correct 43 ms 36128 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 752 ms 4032 KB Output is correct
2 Correct 872 ms 3916 KB Output is correct
3 Correct 746 ms 3992 KB Output is correct
4 Correct 741 ms 4072 KB Output is correct
5 Correct 719 ms 3992 KB Output is correct
6 Correct 17 ms 35320 KB Output is correct
7 Correct 15 ms 35348 KB Output is correct
8 Correct 15 ms 35284 KB Output is correct
9 Correct 53 ms 36116 KB Output is correct
10 Correct 10 ms 25300 KB Output is correct
11 Correct 10 ms 25300 KB Output is correct
12 Correct 65 ms 26932 KB Output is correct
13 Correct 9 ms 25300 KB Output is correct
14 Correct 10 ms 25300 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 55 ms 1484 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 4030 ms 4024 KB Output is correct
28 Correct 12986 ms 213516 KB Output is correct
29 Correct 10004 ms 210192 KB Output is correct
30 Correct 9866 ms 210252 KB Output is correct
31 Correct 13924 ms 215156 KB Output is correct
32 Correct 1 ms 340 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 730 ms 3896 KB Output is correct
2 Correct 875 ms 3972 KB Output is correct
3 Correct 739 ms 4092 KB Output is correct
4 Correct 737 ms 4096 KB Output is correct
5 Correct 726 ms 4088 KB Output is correct
6 Correct 17 ms 35412 KB Output is correct
7 Correct 18 ms 35344 KB Output is correct
8 Correct 18 ms 35340 KB Output is correct
9 Correct 47 ms 36228 KB Output is correct
10 Correct 11 ms 25356 KB Output is correct
11 Correct 11 ms 25284 KB Output is correct
12 Correct 65 ms 27036 KB Output is correct
13 Correct 11 ms 25368 KB Output is correct
14 Correct 11 ms 25268 KB Output is correct
15 Execution timed out 20037 ms 199392 KB Time limit exceeded
16 Halted 0 ms 0 KB -