답안 #16001 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16001	2015-08-05T07:51:45 Z	tonyjjw	포탈들 (BOI14_portals)	C++14	39 / 100	995 ms	190076 KB

portals

//*
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
#define MN 1000
#define pb push_back
#pragma warning(disable:4996)
using namespace std;

int N,M;
char map[MN+2][MN+3];

struct PAIR{
	int x,y;
	PAIR(){}
	PAIR(int x_,int y_){
		x=x_,y=y_;
	}
	PAIR operator +(PAIR A)const{
		return PAIR(x+A.x,y+A.y);
	}
};

PAIR mp(int x,int y){
	return PAIR(x,y);
}

PAIR left[MN+2][MN+2],right[MN+2][MN+2],up[MN+2][MN+2],down[MN+2][MN+2],st,ed;
vector<PAIR> dir;
int wall_dist[MN+2][MN+2],visit[MN+2][MN+2],dist[MN+2][MN+2];
vector<PAIR> E[MN+2][MN+2];
vector<int> C[MN+2][MN+2];

int hsize;
struct HEAP{
	PAIR p;
	int d;
	HEAP(){}
	HEAP(PAIR p_,int d_){
		p=p_,d=d_;
	}
	bool operator <(HEAP A)const{
		return d>A.d;
	}
}H[MN*MN];

void push(PAIR p,int d){
	H[hsize++]=HEAP(p,d);
	push_heap(H,H+hsize);
}
void pop(){
	pop_heap(H,H+hsize);
	hsize--;
}

bool wall_check(PAIR a){
	return map[a.x][a.y]=='#';
}

int main(){
	dir.pb(mp(0,1)),dir.pb(mp(0,-1)),dir.pb(mp(1,0)),dir.pb(mp(-1,0));

//	freopen("input.txt","r",stdin),freopen("output.txt","w",stdout);
	scanf("%d%d",&N,&M);
	for(int i=0;i<=N+1;i++)for(int j=0;j<=M+1;j++)map[i][j]='#';
	for(int i=1;i<=N;i++)scanf("%s",map[i]+1);
	for(int i=1;i<=N;i++)map[i][M+1]='#';
	for(int i=1;i<=N;i++)for(int j=1;j<=M;j++){
		if(map[i][j]=='S')st=mp(i,j);
		if(map[i][j]=='C')ed=mp(i,j);
	}
	for(int i=1;i<=N;i++)for(int j=1;j<=M;j++){
		left[i][j]=(map[i][j-1]=='#')?mp(i,j):left[i][j-1];
		up[i][j]=(map[i-1][j]=='#')?mp(i,j):up[i-1][j];
	}
	for(int i=N;i>=1;i--)for(int j=M;j>=1;j--){
		right[i][j]=(map[i][j+1]=='#')?mp(i,j):right[i][j+1];
		down[i][j]=(map[i+1][j]=='#')?mp(i,j):down[i+1][j];
	}

	queue<PAIR> que;
	for(int i=0;i<=N+1;i++)for(int j=0;j<=M+1;j++){
		if(map[i][j]=='#'){
			que.push(mp(i,j));
			visit[i][j]=1;
		}
	}
	while(!que.empty()){
		auto h=que.front(); que.pop();
		for(auto d:dir){
			auto next=h+d;
			if(next.x<0 || next.x>N+1 || next.y<0 || next.y>M+1)continue;
			if(visit[next.x][next.y] || map[next.x][next.y]=='#')continue;
			visit[next.x][next.y]=1;
			wall_dist[next.x][next.y]=wall_dist[h.x][h.y]+1;
			que.push(next);
		}
	}
	for(int i=1;i<=N;i++)for(int j=1;j<=M;j++){
		if(wall_check(mp(i,j)))continue;
		if(!wall_check(left[i][j])){
			E[i][j].pb(left[i][j]);
			C[i][j].pb(wall_dist[i][j]);
		}
		if(!wall_check(right[i][j])){
			E[i][j].pb(right[i][j]);
			C[i][j].pb(wall_dist[i][j]);
		}
		if(!wall_check(up[i][j])){
			E[i][j].pb(up[i][j]);
			C[i][j].pb(wall_dist[i][j]);
		}
		if(!wall_check(down[i][j])){
			E[i][j].pb(down[i][j]);
			C[i][j].pb(wall_dist[i][j]);
		}
		for(auto d:dir){
			if(!wall_check(mp(i,j)+d)){
				E[i][j].pb(mp(i,j)+d);
				C[i][j].pb(1);
			}
		}
	}
	for(int i=1;i<=N;i++)for(int j=1;j<=M;j++){
		visit[i][j]=0;
		dist[i][j]=1e9;
	}

	push(st,0);
	while(hsize){
		auto top=H[0];
		pop();
		if(visit[top.p.x][top.p.y])continue;
		visit[top.p.x][top.p.y]=1;
		dist[top.p.x][top.p.y]=top.d;
		for(int i=0;i<E[top.p.x][top.p.y].size();i++){
			auto t=E[top.p.x][top.p.y][i];
			auto c=C[top.p.x][top.p.y][i];
			push(t,top.d+c);
		}
	}
	printf("%d",dist[ed.x][ed.y]);

	return 0;
}
//*/

Subtask #1
0.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	0 ms	0 KB	Couldn't start child /var/www/temp/16001/ji9VeJEFKI9SLo0
2	Halted	0 ms	0 KB	-

Subtask #2
0.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	0 ms	4200 KB	open (syscall #2) was called by the program (disallowed syscall)
2	Halted	0 ms	0 KB	-

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	104488 KB	Output is correct
2	Correct	14 ms	104488 KB	Output is correct
3	Correct	12 ms	104488 KB	Output is correct
4	Correct	11 ms	104488 KB	Output is correct
5	Correct	38 ms	107260 KB	Output is correct
6	Correct	45 ms	107392 KB	Output is correct
7	Correct	53 ms	107656 KB	Output is correct
8	Correct	37 ms	107788 KB	Output is correct

Subtask #4
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	104488 KB	Output is correct
2	Correct	14 ms	104488 KB	Output is correct
3	Correct	8 ms	104488 KB	Output is correct
4	Correct	8 ms	104488 KB	Output is correct
5	Correct	11 ms	104488 KB	Output is correct
6	Correct	13 ms	104488 KB	Output is correct
7	Correct	4 ms	104488 KB	Output is correct
8	Correct	14 ms	104488 KB	Output is correct
9	Correct	14 ms	104752 KB	Output is correct
10	Correct	11 ms	104752 KB	Output is correct
11	Correct	12 ms	104620 KB	Output is correct
12	Correct	6 ms	104620 KB	Output is correct
13	Correct	8 ms	104620 KB	Output is correct
14	Correct	28 ms	107260 KB	Output is correct
15	Correct	40 ms	107392 KB	Output is correct
16	Correct	45 ms	107656 KB	Output is correct
17	Correct	36 ms	107644 KB	Output is correct
18	Correct	51 ms	108288 KB	Output is correct
19	Correct	83 ms	109372 KB	Output is correct
20	Correct	78 ms	109372 KB	Output is correct
21	Correct	30 ms	107392 KB	Output is correct
22	Correct	33 ms	107392 KB	Output is correct
23	Correct	40 ms	107524 KB	Output is correct
24	Correct	71 ms	109372 KB	Output is correct
25	Correct	9 ms	104488 KB	Output is correct
26	Correct	10 ms	104620 KB	Output is correct
27	Correct	4 ms	104488 KB	Output is correct
28	Correct	29 ms	107788 KB	Output is correct

Subtask #5
0.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	104488 KB	Output is correct
2	Correct	10 ms	104488 KB	Output is correct
3	Correct	9 ms	104488 KB	Output is correct
4	Correct	7 ms	104488 KB	Output is correct
5	Correct	8 ms	104488 KB	Output is correct
6	Correct	7 ms	104488 KB	Output is correct
7	Correct	17 ms	104488 KB	Output is correct
8	Correct	4 ms	104488 KB	Output is correct
9	Correct	11 ms	104752 KB	Output is correct
10	Correct	8 ms	104752 KB	Output is correct
11	Correct	10 ms	104620 KB	Output is correct
12	Correct	12 ms	104620 KB	Output is correct
13	Correct	8 ms	104620 KB	Output is correct
14	Correct	23 ms	107260 KB	Output is correct
15	Correct	54 ms	107392 KB	Output is correct
16	Correct	35 ms	107656 KB	Output is correct
17	Correct	46 ms	107644 KB	Output is correct
18	Correct	46 ms	108288 KB	Output is correct
19	Correct	78 ms	109372 KB	Output is correct
20	Correct	86 ms	109372 KB	Output is correct
21	Correct	31 ms	107392 KB	Output is correct
22	Correct	29 ms	107392 KB	Output is correct
23	Correct	45 ms	107524 KB	Output is correct
24	Incorrect	995 ms	190076 KB	Output isn't correct - wrong output format : File not found: "/var/www/temp/16001/outputQrc5_1"
25	Halted	0 ms	0 KB	-

답안 #16001

Compilation message

Subtask #1 0.0 / 11.0

Subtask #2 0.0 / 20.0

Subtask #3 20.0 / 20.0

Subtask #4 19.0 / 19.0

Subtask #5 0.0 / 30.0

Subtask #1
0.0 / 11.0

Subtask #2
0.0 / 20.0

Subtask #3
20.0 / 20.0

Subtask #4
19.0 / 19.0

Subtask #5
0.0 / 30.0