【BZOJ 4356】[CEOI2014] Wall






#define LL long long
using namespace std;

const int L = 400 + 9;
const int N = L * L * 4;
const int M = N * 4;
const LL INF = 1e17;

int n,m,tot,E,head[N],nxt[M],to[M],cost[M];
int cx[L][L],cy[L][L],intree[L][L];
int dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1};
bool del[L][L][4],vis[L][L],done[N],bst[L][L][4];
LL dis[N];
priority_queue<pair<LL, int> > que;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;

inline void Add_Edge(int u, int v, int c) {
	to[++E] = v; nxt[E] = head[u]; head[u] = E; cost[E] = c;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; cost[E] = c;

inline int id(int x, int y, int t = 0) {
	if (!t) return x + (y - 1) * (n + 1);
	else return (x - 1 + (y - 1) * (n + 1) << 2) + t;

inline void Dijkstra(int s) {
	memset(done, 0, sizeof(done));
	fill(dis, dis+N, INF); dis[s] = 0;
	que.push(make_pair(0, s));
	for (int w;!que.empty();) {
		w = que.top().second; que.pop(); 
		if (done[w]) continue;
		done[w] = 1;
		for (int i=head[w];i;i=nxt[i]) {
			if (dis[to[i]] > dis[w] + cost[i]) {
				dis[to[i]] = dis[w] + cost[i];
				que.push(make_pair(-dis[to[i]], to[i]));

bool mark(int x, int y, int f) {
	if (intree[x][y]) return ~intree[x][y]?1:0;
	bool tag = vis[x][y]; 
	for (int w=id(x,y),i=head[w];i;i=nxt[i]) {
		if (dis[w] + cost[i] == dis[to[i]] && to[i] != f) {
			for (int j=1,nx,ny;j<=4;j++) {
				nx = x + dx[j]; ny = y + dy[j];
				if (id(nx, ny) == to[i]) {
					if (mark(nx, ny, w)) {
						bst[x][y][j] = tag = 1;
						bst[nx][ny][j+2>4?j-2:j+2] = 1;
	intree[x][y] = tag?1:-1;
	return tag;

int main() {
	m = read(); n = read();
	del[1][1][2] = del[1][1][4] = 1;
	for (int j=1;j<=m;j++) {
		for (int i=1;i<=n;i++) {
			if (read()) {
				vis[i][j] = 1;
				del[i][j][4] = 1;
				del[i+1][j][3] = 1;
				del[i][j+1][1] = 1;
				del[i+1][j+1][2] = 1;
	for (int j=1,tmp;j<=m;j++) {
		for (int i=1;i<=n+1;i++) {
			cy[i][j] = tmp = read();
			Add_Edge(id(i, j), id(i, j+1), tmp);
	for (int j=1,tmp;j<=m+1;j++) {
		for (int i=1;i<=n;i++) {
			cx[i][j] = tmp = read();
			Add_Edge(id(i, j), id(i+1, j), tmp);
	mark(1, 1, id(1, 1));  
	E = 0; memset(head,0,sizeof(head));
	for (int j=1;j<=m+1;j++) {
		for (int i=1;i<=n+1;i++) {
			if (!del[i][j][1]) {
				if (!del[i][j][4] && !bst[i][j][1]) Add_Edge(id(i, j, 1), id(i, j, 4), 0);
				if (i <= n && !del[i+1][j][2]) Add_Edge(id(i, j, 1), id(i+1, j, 2), cx[i][j]);
			if (!del[i][j][2]) {
				if (!del[i][j][1] && !bst[i][j][4]) Add_Edge(id(i, j, 2), id(i, j, 1), 0);
				if (!del[i][j][3] && !bst[i][j][3]) Add_Edge(id(i, j, 2), id(i, j, 3), 0);
			if (!del[i][j][3]) {
				if (!del[i][j][4] && !bst[i][j][2]) Add_Edge(id(i, j, 3), id(i, j, 4), 0);
				if (j <= m && !del[i][j+1][2]) Add_Edge(id(i, j, 3), id(i, j+1, 2), cy[i][j]);
			if (!del[i][j][4]) {
				if (i <= n && !del[i+1][j][3]) Add_Edge(id(i, j, 4), id(i+1, j, 3), cx[i][j]);
				if (j <= m && !del[i][j+1][1]) Add_Edge(id(i, j, 4), id(i, j+1, 1), cy[i][j]);
	return 0;

27 thoughts to “【BZOJ 4356】[CEOI2014] Wall”

  1. Hi there! Quick question that’s entirely off topic.
    Do you know how to make your site mobile friendly? My weblog
    looks weird when browsing from my iphone4. I’m trying to find a
    theme or plugin that might be able to correct this problem.
    If you have any recommendations, please share. Cheers!

  2. What i do not understood is if truth be told how you are now not actually
    much more well-appreciated than you might be now.
    You are so intelligent. You already know therefore significantly in relation to this subject, made me
    in my opinion imagine it from a lot of numerous angles.
    Its like men and women are not interested except it’s something to do
    with Woman gaga! Your personal stuffs outstanding. All the time care for it

  3. Hey There. I found your blog using msn. This is a really well written article.
    I will be sure to bookmark it and come back to read more of your useful info.
    Thanks for the post. I’ll certainly return.

  4. This is very interesting, You’re a very skilled blogger.
    I’ve joined your rss feed and look forward to in the hunt for
    more of your magnificent post. Additionally, I’ve
    shared your web site in my social networks

  5. I’m not that much of a internet reader to be honest but your blogs really nice, keep
    it up! I’ll go ahead and bookmark your site to
    come back later. All the best

  6. Hey there! This post could not be written any better!
    Reading this post reminds me of my good old room mate!

    He always kept talking about this. I will forward this write-up to him.
    Fairly certain he will have a good read. Many thanks for sharing!

  7. Thanks for the marvelous posting! I certainly enjoyed reading it, you may be a great author.
    I will make sure to bookmark your blog and will often come back someday.
    I want to encourage you to continue your great work, have a nice day!

  8. Hey there! This post could not be written any better!
    Reading through this post reminds me of my previous room mate!

    He always kept chatting about this. I will forward this write-up to him.
    Fairly certain he will have a good read. Thank you for sharing!

  9. Wonderful web site. A lot of useful information here. I’m sending it to some
    pals ans additionally sharing in delicious. And naturally, thanks on your sweat!

  10. Superb website you have here but I was wanting to
    know if you knew of any discussion boards that cover the same topics
    discussed here? I’d really love to be a part of community where I
    can get feed-back from other experienced people that
    share the same interest. If you have any recommendations, please let me know.

  11. I really like what you guys are usually up too. Such clever
    work and exposure! Keep up the very good works guys I’ve incorporated you guys
    to our blogroll.

  12. Hey there! I just wanted to ask if you ever have any
    problems with hackers? My last blog (wordpress) was hacked and I ended up losing a few months of
    hard work due to no backup. Do you have any methods to protect against hackers?

  13. Asking questions are really good thing if you are not understanding anything completely, however this piece of writing presents good understanding even.

Leave a Reply

Your email address will not be published. Required fields are marked *