| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 25966 |
2017-06-25T09:02:01 Z |
구재현(#1094) |
Wall (CEOI14_wall) |
C++ |
|
626 ms |
40384 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);
for(int i=0; i<2*n+2; i++){
for(int j=0; j<=2*m+2; j++){
if(lx2[i][j]>1000) printf("# ");
else printf("%d ", lx2[i][j]);
}
puts("");
}
for(int i=0; i<=2*n+2; i++){
for(int j=0; j<2*m+2; j++){
if(ly2[i][j]>1000) printf("# ");
else printf("%d ", ly2[i][j]);
}
puts("");
}
cout << dist[0][1];
}
Compilation message
wall.cpp: In function 'void dijkstra(lint (*)[805], lint (*)[805], int, int, int, int)':
wall.cpp:69:10: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
pq.push({s,e,0});
^
wall.cpp:69:17: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
pq.push({s,e,0});
^
wall.cpp:78:12: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
pq.push({t.x + 1, t.y, dist[t.x+1][t.y]});
^
wall.cpp:78:44: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
pq.push({t.x + 1, t.y, dist[t.x+1][t.y]});
^
wall.cpp:83:12: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
pq.push({t.x, t.y + 1, dist[t.x][t.y+1]});
^
wall.cpp:83:44: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
pq.push({t.x, t.y + 1, dist[t.x][t.y+1]});
^
wall.cpp:88:12: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
pq.push({t.x - 1, t.y, dist[t.x-1][t.y]});
^
wall.cpp:88:44: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
pq.push({t.x - 1, t.y, dist[t.x-1][t.y]});
^
wall.cpp:93:12: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
pq.push({t.x, t.y - 1, dist[t.x][t.y-1]});
^
wall.cpp:93:44: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
pq.push({t.x, t.y - 1, dist[t.x][t.y-1]});
^
wall.cpp: In function 'int main()':
wall.cpp:194:32: warning: format '%d' expects argument of type 'int', but argument 2 has type 'lint {aka long long int}' [-Wformat=]
else printf("%d ", lx2[i][j]);
^
wall.cpp:201:32: warning: format '%d' expects argument of type 'int', but argument 2 has type 'lint {aka long long int}' [-Wformat=]
else printf("%d ", ly2[i][j]);
^
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]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
33992 KB |
Output isn't correct |
| 2 |
Incorrect |
6 ms |
33992 KB |
Output isn't correct |
| 3 |
Incorrect |
3 ms |
33992 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
33992 KB |
Output isn't correct |
| 5 |
Incorrect |
0 ms |
33992 KB |
Output isn't correct |
| 6 |
Incorrect |
6 ms |
33992 KB |
Output isn't correct |
| 7 |
Incorrect |
13 ms |
33992 KB |
Output isn't correct |
| 8 |
Incorrect |
6 ms |
33992 KB |
Output isn't correct |
| 9 |
Incorrect |
6 ms |
33992 KB |
Output isn't correct |
| 10 |
Incorrect |
6 ms |
34132 KB |
Output isn't correct |
| 11 |
Incorrect |
6 ms |
33992 KB |
Output isn't correct |
| 12 |
Incorrect |
6 ms |
33992 KB |
Output isn't correct |
| 13 |
Incorrect |
6 ms |
33992 KB |
Output isn't correct |
| 14 |
Incorrect |
6 ms |
33992 KB |
Output isn't correct |
| 15 |
Incorrect |
9 ms |
34132 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
33992 KB |
Output isn't correct |
| 2 |
Incorrect |
13 ms |
33992 KB |
Output isn't correct |
| 3 |
Incorrect |
3 ms |
33992 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
34132 KB |
Output isn't correct |
| 5 |
Incorrect |
3 ms |
33992 KB |
Output isn't correct |
| 6 |
Incorrect |
6 ms |
33992 KB |
Output isn't correct |
| 7 |
Incorrect |
6 ms |
33992 KB |
Output isn't correct |
| 8 |
Incorrect |
13 ms |
33992 KB |
Output isn't correct |
| 9 |
Incorrect |
6 ms |
33992 KB |
Output isn't correct |
| 10 |
Incorrect |
6 ms |
34132 KB |
Output isn't correct |
| 11 |
Incorrect |
9 ms |
33992 KB |
Output isn't correct |
| 12 |
Incorrect |
6 ms |
33992 KB |
Output isn't correct |
| 13 |
Incorrect |
3 ms |
33992 KB |
Output isn't correct |
| 14 |
Incorrect |
9 ms |
33992 KB |
Output isn't correct |
| 15 |
Incorrect |
3 ms |
34132 KB |
Output isn't correct |
| 16 |
Incorrect |
3 ms |
34132 KB |
Output isn't correct |
| 17 |
Incorrect |
3 ms |
34132 KB |
Output isn't correct |
| 18 |
Incorrect |
6 ms |
33992 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
86 ms |
34460 KB |
Output isn't correct |
| 2 |
Incorrect |
79 ms |
33992 KB |
Output isn't correct |
| 3 |
Incorrect |
66 ms |
34132 KB |
Output isn't correct |
| 4 |
Incorrect |
93 ms |
35612 KB |
Output isn't correct |
| 5 |
Incorrect |
146 ms |
34132 KB |
Output isn't correct |
| 6 |
Incorrect |
86 ms |
34132 KB |
Output isn't correct |
| 7 |
Incorrect |
246 ms |
34844 KB |
Output isn't correct |
| 8 |
Incorrect |
246 ms |
34132 KB |
Output isn't correct |
| 9 |
Incorrect |
189 ms |
34132 KB |
Output isn't correct |
| 10 |
Incorrect |
309 ms |
35624 KB |
Output isn't correct |
| 11 |
Incorrect |
313 ms |
37164 KB |
Output isn't correct |
| 12 |
Incorrect |
73 ms |
33992 KB |
Output isn't correct |
| 13 |
Incorrect |
196 ms |
34264 KB |
Output isn't correct |
| 14 |
Incorrect |
276 ms |
34844 KB |
Output isn't correct |
| 15 |
Incorrect |
389 ms |
34132 KB |
Output isn't correct |
| 16 |
Incorrect |
356 ms |
34264 KB |
Output isn't correct |
| 17 |
Incorrect |
546 ms |
37224 KB |
Output isn't correct |
| 18 |
Incorrect |
626 ms |
40384 KB |
Output isn't correct |
| 19 |
Incorrect |
493 ms |
35612 KB |
Output isn't correct |
| 20 |
Incorrect |
403 ms |
34264 KB |
Output isn't correct |
