oj.uz

Submission #415263

# Submission time Handle Problem Language Result Execution time Memory
415263 2021-05-31T18:52:14 Z sinamhdv Wall (CEOI14_wall) C++11
100 / 100
 529 ms 87316 KB 
// CEOI14_wall
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 420
#define MAXG (MAXN * MAXN * 4)

int ngb[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};	// 0123 => URDL

int n, m;
bool vil[MAXN][MAXN];
int cost[4][MAXN][MAXN];
ll dist[MAXN][MAXN];
int par[MAXN][MAXN];
bool mark[4][MAXN][MAXN], lmk[4][MAXN][MAXN];

ll d[MAXG];
vector<pii> adj[MAXG];

void dij(int x, int y)
{
	FOR(i, 0, MAXN) fill(dist[i], dist[i] + MAXN, LINF);
	dist[x][y] = 0;
	priority_queue<pair<ll, pii>, vector<pair<ll, pii>>, greater<pair<ll, pii>>> s;
	s.push({0, {x, y}});
	while (!s.empty())
	{
		int x, y;
		auto p = s.top();
		s.pop();
		tie(x, y) = p.sc;
		if (dist[x][y] != p.fr) continue;
		FOR(i, 0, 4)
		{
			int ux = x + ngb[i][0];
			int uy = y + ngb[i][1];
			if (ux < 0 || uy < 0 || ux > n || uy > m) continue;
			int w = cost[i][x][y];
			if (dist[x][y] + w >= dist[ux][uy]) continue;
			par[ux][uy] = (i % 2 ? 4 - i : 2 - i);
			dist[ux][uy] = dist[x][y] + w;
			s.push({dist[ux][uy], {ux, uy}});
		}
	}
}

inline int get(int i, int x, int y)
{
	return (x * (m + 1) + y) * 4 + i;
}

inline void addedge(int d1, int x1, int y1, int d2, int x2, int y2, int w)
{
	int u = get(d1, x1, y1);
	int v = get(d2, x2, y2);

//	if (w == 0) cout << "small: " << d1 << ' ' << x1 << ' ' << y1 << " => " << d2 << ' ' << x2 << ' ' << y2 << endl;
//	if (w) cout << "long: " << d1 << ' ' << x1 << ' ' << y1 << " => " << d2 << ' ' << x2 << ' ' << y2 << "   | w = " << w << endl;
	
	adj[u].pb({v, w});
	adj[v].pb({u, w});
}

int32_t main(void)
{
	fast_io;
	cin >> n >> m;
	FOR(i, 0, n) FOR(j, 0, m) cin >> vil[i][j];
	FOR(i, 0, n) FOR(j, 0, m + 1) cin >> cost[2][i][j], cost[0][i + 1][j] = cost[2][i][j];
	FOR(i, 0, n + 1) FOR(j, 0, m) cin >> cost[1][i][j], cost[3][i][j + 1] = cost[1][i][j];

	dij(0, 0);

//	FOR(i, 0, n + 1) dbgr(dist[i], dist[i] + m + 1);

	FOR(i, 0, n) FOR(j, 0, m) if (vil[i][j])
	{
		// handle village
		mark[1][i][j] = mark[2][i][j] = true;
		mark[2][i][j + 1] = mark[3][i][j + 1] = true;
		mark[0][i + 1][j] = mark[1][i + 1][j] = true;
		mark[0][i + 1][j + 1] = mark[3][i + 1][j + 1] = true;

		lmk[1][i][j] = lmk[0][i + 1][j] = lmk[2][i][j + 1] = lmk[3][i + 1][j + 1] = true;

		// trace path
		int x = i, y = j;
		while (x || y)
		{
			mark[par[x][y]][x][y] = true;
			int rev = (par[x][y] % 2 ? 4 - par[x][y] : 2 - par[x][y]);
			int px = x + ngb[par[x][y]][0];
			int py = y + ngb[par[x][y]][1];
			mark[rev][px][py] = true;
			x = px, y = py;
		}
	}

	mark[0][0][0] = mark[3][0][0] = true;

	// construct graph
	FOR(x, 0, n + 1) FOR(y, 0, m + 1)
	{
		// small edges
		FOR(i, 0, 4) if (!mark[(i + 1) % 4][x][y]) addedge(i, x, y, (i + 1) % 4, x, y, 0);

		// long edges
		FOR(i, 0, 4) if (!lmk[i][x][y])
		{
			int ux = x + ngb[i][0];
			int uy = y + ngb[i][1];
			if (!(ux < 0 || uy < 0 || ux > n || uy > m))
				addedge(i, x, y, (i + 1) % 4, ux, uy, cost[i][x][y]);
			
			int j = (i + 1) % 4;
			ux = x + ngb[j][0];
			uy = y + ngb[j][1];
			if (!(ux < 0 || uy < 0 || ux > n || uy > m))
				addedge(i, x, y, (3 + i) % 4, ux, uy, cost[j][x][y]);
		}
	}

	// final dij
	fill(d, d + MAXG, LINF);
	int r = get(0, 0, 0);
	d[r] = 0;
	priority_queue<pll, vector<pll>, greater<pll>> s;
	s.push({0, r});
	
	while (!s.empty())
	{
		pll p = s.top();
		s.pop();
		int v = p.sc;
		if (d[v] != p.fr) continue;
		for (pii p : adj[v])
		{
			int u = p.fr, w = p.sc;
			if (d[v] + w >= d[u]) continue;
			d[u] = d[v] + w;
			s.push({d[u], u});
		}
	}

	cout << d[get(2, 0, 0)] << endl;
	
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23884 KB Output is correct
2 Correct 14 ms 23928 KB Output is correct
3 Correct 14 ms 23884 KB Output is correct
4 Correct 14 ms 23884 KB Output is correct
5 Correct 17 ms 23884 KB Output is correct
6 Correct 17 ms 24448 KB Output is correct
7 Correct 16 ms 24444 KB Output is correct
8 Correct 16 ms 24396 KB Output is correct
9 Correct 18 ms 24292 KB Output is correct
10 Correct 17 ms 24524 KB Output is correct
11 Correct 16 ms 24604 KB Output is correct
12 Correct 20 ms 24648 KB Output is correct
13 Correct 17 ms 24780 KB Output is correct
14 Correct 21 ms 24728 KB Output is correct
15 Correct 16 ms 24596 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24712 KB Output is correct
2 Correct 18 ms 24836 KB Output is correct
3 Correct 20 ms 24820 KB Output is correct
4 Correct 20 ms 24720 KB Output is correct
5 Correct 18 ms 24780 KB Output is correct
6 Correct 17 ms 24780 KB Output is correct
7 Correct 20 ms 24788 KB Output is correct
8 Correct 19 ms 24780 KB Output is correct
9 Correct 19 ms 24652 KB Output is correct
10 Correct 18 ms 24796 KB Output is correct
11 Correct 18 ms 24704 KB Output is correct
12 Correct 20 ms 24780 KB Output is correct
13 Correct 20 ms 24780 KB Output is correct
14 Correct 20 ms 24836 KB Output is correct
15 Correct 20 ms 24780 KB Output is correct
16 Correct 21 ms 24840 KB Output is correct
17 Correct 21 ms 24824 KB Output is correct
18 Correct 17 ms 24780 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 39220 KB Output is correct
2 Correct 91 ms 36832 KB Output is correct
3 Correct 93 ms 37572 KB Output is correct
4 Correct 105 ms 38372 KB Output is correct
5 Correct 261 ms 50788 KB Output is correct
6 Correct 112 ms 38976 KB Output is correct
7 Correct 254 ms 58488 KB Output is correct
8 Correct 226 ms 57284 KB Output is correct
9 Correct 213 ms 57040 KB Output is correct
10 Correct 273 ms 59104 KB Output is correct
11 Correct 260 ms 61152 KB Output is correct
12 Correct 90 ms 37996 KB Output is correct
13 Correct 235 ms 55764 KB Output is correct
14 Correct 441 ms 74300 KB Output is correct
15 Correct 408 ms 79560 KB Output is correct
16 Correct 381 ms 80772 KB Output is correct
17 Correct 447 ms 83656 KB Output is correct
18 Correct 529 ms 87316 KB Output is correct
19 Correct 456 ms 81060 KB Output is correct
20 Correct 405 ms 79100 KB Output is correct