Submission #415263

#	Time	Username	Problem	Language	Result	Execution time	Memory
415263		sinamhdv	Wall (CEOI14_wall)	C++11	100 / 100	529 ms	87316 KiB

wall

// 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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40