oj.uz

Submission #25716

# Submission time Handle Problem Language Result Execution time Memory
25716 2017-06-23T19:02:27 Z gs14004 Wall (CEOI14_wall) C++11
100 / 100
 489 ms 40380 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

int n, m, px = -1, py = -1;
int a[405][405];
lint lx[805][805], ly[805][805];
bool cx[405][405], cy[405][405];

bool vis[805][805];
lint dist[805][805];
pi par[805][805];

struct edg{
	int x, y;
	lint cst;
	bool operator<(const edg &a)const{
		return cst > a.cst;
	}
};

priority_queue<edg> pq;

void input(){
	scanf("%d %d",&n,&m);
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			scanf("%d",&a[i][j]);
			if(a[i][j] && px == -1){
				px = i, py = j;
			}
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<=m; j++){
			scanf("%lld",&lx[i][j]);
		}
	}
	for(int i=0; i<=n; i++){
		for(int j=0; j<m; j++){
			scanf("%lld",&ly[i][j]);
		}
	}
}

void dijkstra(lint lx[805][805], lint ly[805][805], int n, int m, int s, int e){
	memset(dist,0x3f,sizeof(dist));
	memset(vis,0,sizeof(vis));
	dist[s][e] = 0;
	pq.push({s,e,0});
	while(!pq.empty()){
		edg t = pq.top();
		pq.pop();
		if(vis[t.x][t.y]) continue;
		vis[t.x][t.y] = 1;
		if(t.x < n && dist[t.x+1][t.y] > t.cst + lx[t.x][t.y]){
			dist[t.x+1][t.y] = t.cst + lx[t.x][t.y];
			par[t.x+1][t.y] = pi(t.x, t.y);
			pq.push({t.x + 1, t.y, dist[t.x+1][t.y]});
		}
		if(t.y < m && dist[t.x][t.y+1] > t.cst + ly[t.x][t.y]){
			dist[t.x][t.y+1] = t.cst + ly[t.x][t.y];
			par[t.x][t.y+1] = pi(t.x, t.y);
			pq.push({t.x, t.y + 1, dist[t.x][t.y+1]});
		}
		if(t.x && dist[t.x-1][t.y] > t.cst + lx[t.x-1][t.y]){
			dist[t.x-1][t.y] = t.cst + lx[t.x-1][t.y];
			par[t.x-1][t.y] = pi(t.x, t.y);
			pq.push({t.x - 1, t.y, dist[t.x-1][t.y]});
		}
		if(t.y && dist[t.x][t.y-1] > t.cst + ly[t.x][t.y-1]){
			dist[t.x][t.y-1] = t.cst + ly[t.x][t.y-1];
			par[t.x][t.y-1] = pi(t.x, t.y);
			pq.push({t.x, t.y - 1, dist[t.x][t.y-1]});
		}
	}
}

lint lx2[805][805], ly2[805][805];

void paintpath(int x, int y){
	if(x == 0 && y == 0) return;
	pi t = par[x][y];
	if(t.first == x-1 && !cx[x-1][y]){
		cx[x-1][y] = 1;
		paintpath(x-1, y);
	}
	if(t.first == x+1 && !cx[x][y]){
		cx[x][y] = 1;
		paintpath(x+1, y);
	}
	if(t.second == y-1 && !cy[x][y-1]){
		cy[x][y-1] = 1;
		paintpath(x, y-1);
	}
	if(t.second == y+1 && !cy[x][y]){
		cy[x][y] = 1;
		paintpath(x, y+1);
	}
}

void add_edge(int sx, int sy, int ex, int ey, int c){
	if(sx != ex){
		lx2[min(sx, ex)][ey] = c;
	}
	if(sy != ey){
		ly2[sx][min(sy, ey)] = c;
	}
}

void make_graph(){
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(a[i][j]) paintpath(i, j);
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(a[i][j]){
				cx[i][j] = cx[i][j+1] = 1;
				cy[i][j] = cy[i+1][j] = 1;
			}
		}
	}
	memset(lx2,0x3f,sizeof(lx2));
	memset(ly2,0x3f,sizeof(ly2));
	for(int i=0; i<n; i++){
		for(int j=0; j<=m; j++){
			add_edge(2*i+1, 2*j, 2*i+2, 2*j, lx[i][j]);
			add_edge(2*i+1, 2*j+1, 2*i+2, 2*j+1, lx[i][j]);
		}
	}
	for(int i=0; i<=n; i++){
		for(int j=0; j<m; j++){
			add_edge(2*i, 2*j+1, 2*i, 2*j+2, ly[i][j]);
			add_edge(2*i+1, 2*j+1, 2*i+1, 2*j+2, ly[i][j]);
		}
	}
	for(int i=0; i<=n; i++){
		for(int j=0; j<=m; j++){
			if(i == 0 && j == 0){
				if(!cx[0][0]){
					add_edge(1, 0, 1, 1, 0);
				}
				if(!cy[0][0]){
					add_edge(0, 1, 1, 1, 0);
				}
			}
			else{
				if(!i || !cx[i-1][j]){
					add_edge(2*i, 2*j, 2*i, 2*j+1, 0);
				}
				if(!j || !cy[i][j-1]){
					add_edge(2*i, 2*j, 2*i+1, 2*j, 0);
				}
				if(i == n || !cx[i][j]){
					add_edge(2*i+1, 2*j, 2*i+1, 2*j+1, 0);
				}
				if(j == m || !cy[i][j]){
					add_edge(2*i, 2*j+1, 2*i+1, 2*j+1, 0);
				}
			}
		}
	}
}

int main(){
	input();
	dijkstra(lx, ly, n, m, 0, 0);
	make_graph();
	dijkstra(lx2, ly2, 2*n+1, 2*m+1, 1, 0);
	cout << dist[0][1];
}

Compilation message

wall.cpp: In function 'void input()':
wall.cpp:44:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
wall.cpp:47:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&a[i][j]);
                        ^
wall.cpp:55:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld",&lx[i][j]);
                           ^
wall.cpp:60:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld",&ly[i][j]);
                           ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33992 KB Output is correct
2 Correct 0 ms 33992 KB Output is correct
3 Correct 0 ms 33992 KB Output is correct
4 Correct 6 ms 33992 KB Output is correct
5 Correct 3 ms 33992 KB Output is correct
6 Correct 0 ms 33992 KB Output is correct
7 Correct 6 ms 33992 KB Output is correct
8 Correct 0 ms 33992 KB Output is correct
9 Correct 0 ms 33992 KB Output is correct
10 Correct 3 ms 34132 KB Output is correct
11 Correct 3 ms 33992 KB Output is correct
12 Correct 0 ms 33992 KB Output is correct
13 Correct 6 ms 33992 KB Output is correct
14 Correct 3 ms 33992 KB Output is correct
15 Correct 6 ms 34132 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33992 KB Output is correct
2 Correct 3 ms 33992 KB Output is correct
3 Correct 0 ms 33992 KB Output is correct
4 Correct 6 ms 34132 KB Output is correct
5 Correct 3 ms 33992 KB Output is correct
6 Correct 0 ms 33992 KB Output is correct
7 Correct 6 ms 33992 KB Output is correct
8 Correct 3 ms 33992 KB Output is correct
9 Correct 3 ms 33992 KB Output is correct
10 Correct 6 ms 34132 KB Output is correct
11 Correct 3 ms 33992 KB Output is correct
12 Correct 0 ms 33992 KB Output is correct
13 Correct 0 ms 33992 KB Output is correct
14 Correct 0 ms 33992 KB Output is correct
15 Correct 3 ms 34132 KB Output is correct
16 Correct 0 ms 34132 KB Output is correct
17 Correct 3 ms 34132 KB Output is correct
18 Correct 0 ms 33992 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 34460 KB Output is correct
2 Correct 46 ms 33992 KB Output is correct
3 Correct 49 ms 34132 KB Output is correct
4 Correct 69 ms 35612 KB Output is correct
5 Correct 86 ms 34132 KB Output is correct
6 Correct 43 ms 34132 KB Output is correct
7 Correct 129 ms 34844 KB Output is correct
8 Correct 116 ms 34132 KB Output is correct
9 Correct 133 ms 34132 KB Output is correct
10 Correct 199 ms 35624 KB Output is correct
11 Correct 243 ms 37168 KB Output is correct
12 Correct 36 ms 33992 KB Output is correct
13 Correct 133 ms 34264 KB Output is correct
14 Correct 163 ms 34844 KB Output is correct
15 Correct 219 ms 34132 KB Output is correct
16 Correct 246 ms 34264 KB Output is correct
17 Correct 443 ms 37220 KB Output is correct
18 Correct 489 ms 40380 KB Output is correct
19 Correct 369 ms 35612 KB Output is correct
20 Correct 236 ms 34264 KB Output is correct