oj.uz

Submission #765165

# Submission time Handle Problem Language Result Execution time Memory
765165 2023-06-24T09:00:48 Z Sohsoh84 Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 194076 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 = 200 + 10;
const ll INF = 1e9 + 10;
const ll LIM = 10;

int n, m, H[MAXN][MAXM], V[MAXN][MAXM], ps[MAXN][MAXM], sg[MAXN / LIM * 2 + 5][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 7 ms 16852 KB Output is correct
2 Correct 7 ms 16852 KB Output is correct
3 Correct 61 ms 18460 KB Output is correct
4 Correct 8 ms 16852 KB Output is correct
5 Correct 8 ms 16888 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 340 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 55 ms 1500 KB Output is correct
12 Correct 2 ms 468 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 790 ms 3440 KB Output is correct
2 Correct 1284 ms 3484 KB Output is correct
3 Correct 832 ms 3496 KB Output is correct
4 Correct 864 ms 3496 KB Output is correct
5 Correct 797 ms 3472 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 5671 ms 3520 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 29780 KB Output is correct
2 Correct 13 ms 29704 KB Output is correct
3 Correct 14 ms 29780 KB Output is correct
4 Correct 41 ms 30476 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 797 ms 3496 KB Output is correct
2 Correct 1250 ms 3488 KB Output is correct
3 Correct 839 ms 3504 KB Output is correct
4 Correct 834 ms 3496 KB Output is correct
5 Correct 803 ms 3476 KB Output is correct
6 Correct 14 ms 29780 KB Output is correct
7 Correct 14 ms 29780 KB Output is correct
8 Correct 14 ms 29796 KB Output is correct
9 Correct 48 ms 30556 KB Output is correct
10 Correct 8 ms 16852 KB Output is correct
11 Correct 7 ms 16788 KB Output is correct
12 Correct 62 ms 18384 KB Output is correct
13 Correct 9 ms 16852 KB Output is correct
14 Correct 8 ms 16904 KB Output is correct
15 Correct 1 ms 340 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 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 56 ms 1416 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 5696 ms 3608 KB Output is correct
28 Correct 17480 ms 111372 KB Output is correct
29 Correct 10215 ms 107180 KB Output is correct
30 Incorrect 9768 ms 106900 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 3488 KB Output is correct
2 Correct 1248 ms 3488 KB Output is correct
3 Correct 858 ms 3540 KB Output is correct
4 Correct 842 ms 3408 KB Output is correct
5 Correct 803 ms 3472 KB Output is correct
6 Correct 14 ms 29748 KB Output is correct
7 Correct 14 ms 29780 KB Output is correct
8 Correct 14 ms 29792 KB Output is correct
9 Correct 42 ms 30552 KB Output is correct
10 Correct 7 ms 16852 KB Output is correct
11 Correct 7 ms 16852 KB Output is correct
12 Correct 61 ms 18416 KB Output is correct
13 Correct 9 ms 16840 KB Output is correct
14 Correct 8 ms 16840 KB Output is correct
15 Correct 11126 ms 193884 KB Output is correct
16 Execution timed out 20087 ms 194076 KB Time limit exceeded
17 Halted 0 ms 0 KB -