oj.uz

Submission #742979

# Submission time Handle Problem Language Result Execution time Memory
742979 2023-05-17T07:12:05 Z Dan4Life Portals (BOI14_portals) C++17
100 / 100
 405 ms 83848 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define sz(a) (int)a.size()
const int mxN = (int)1e3+10;
using ar = array<int,3>;
int X[] = {1,-1,0,0};
int Y[] = {0,0,1,-1};

string a[mxN];
bool vis[mxN][mxN];
int n, m, stX, stY, enX, enY;
pair<int,int> dir[4][mxN][mxN];
int dis[mxN][mxN], sh[mxN][mxN];
priority_queue<ar,vector<ar>,greater<ar>> pq;

bool valid(int i, int j){
	return i>=0 and j>=0 and i<n and j<m and a[i][j]!='#';
}

void bfs(int sti, int stj){
	memset(dis,63,sizeof(dis));
	pq.push({0,sti,stj}); dis[sti][stj] = 0;
	while(!pq.empty()){
		auto [w,i,j] = pq.top();  pq.pop();
		if(vis[i][j]) continue; vis[i][j]=1;
		for(int k = 0; k < 4; k++){
			int ni = i+X[k], nj = j+Y[k];
			if(valid(ni,nj) and dis[ni][nj]>dis[i][j]+1)
				dis[ni][nj] = dis[i][j]+1, pq.push({dis[ni][nj],ni,nj});
		}
		for(int k = 0; k < 4; k++){
			auto [ni,nj] = dir[k][i][j];
			if(valid(ni,nj) and dis[ni][nj]>dis[i][j]+sh[i][j])
				dis[ni][nj] = dis[i][j]+sh[i][j], pq.push({dis[ni][nj],ni,nj});
		}
	}
}

int32_t main(){
	cin >> n >> m; memset(sh,63,sizeof(sh));
	for(int i = 0; i < n; i++){
		cin >> a[i];
		for(int j = 0; j < m; j++){
			if(a[i][j]=='C') enX=i,enY=j;
			else if(a[i][j]=='S') stX=i,stY=j;
		}
	}
	for(int i = 0; i < n; i++){
		int last = 0;
		for(int j = 0; j < m; j++){
			if(a[i][j]=='#') last = j+1;
			else dir[0][i][j]={i,last},sh[i][j]=min(sh[i][j],abs(last-j)+1);
		}
		last = m-1;
		for(int j = m-1; j >= 0; j--){
			if(a[i][j]=='#') last = j-1;
			else dir[1][i][j]={i,last},sh[i][j]=min(sh[i][j],abs(last-j)+1);
		}
	}
	for(int j = 0; j < m; j++){
		int last = 0;
		for(int i = 0; i < n; i++){
			if(a[i][j]=='#') last = i+1;
			else dir[2][i][j]={last,j},sh[i][j]=min(sh[i][j],abs(last-i)+1);
		}
		last = n-1;
		for(int i = n-1; i >= 0; i--){
			if(a[i][j]=='#') last = i-1;
			else dir[3][i][j]={last,j},sh[i][j]=min(sh[i][j],abs(last-i)+1);
		}
	}
	bfs(stX,stY); cout << dis[enX][enY];
}

Compilation message

portals.cpp: In function 'void bfs(long long int, long long int)':
portals.cpp:27:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   27 |   if(vis[i][j]) continue; vis[i][j]=1;
      |   ^~
portals.cpp:27:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   27 |   if(vis[i][j]) continue; vis[i][j]=1;
      |                           ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16340 KB Output is correct
2 Correct 9 ms 16400 KB Output is correct
3 Correct 8 ms 16408 KB Output is correct
4 Correct 7 ms 16336 KB Output is correct
5 Correct 9 ms 16468 KB Output is correct
6 Correct 8 ms 16468 KB Output is correct
7 Correct 7 ms 16468 KB Output is correct
8 Correct 7 ms 16416 KB Output is correct
9 Correct 7 ms 16340 KB Output is correct
10 Correct 7 ms 16340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16276 KB Output is correct
2 Correct 7 ms 16468 KB Output is correct
3 Correct 7 ms 16468 KB Output is correct
4 Correct 8 ms 16340 KB Output is correct
5 Correct 9 ms 16488 KB Output is correct
6 Correct 10 ms 16416 KB Output is correct
7 Correct 9 ms 16468 KB Output is correct
8 Correct 9 ms 16600 KB Output is correct
9 Correct 11 ms 17236 KB Output is correct
10 Correct 9 ms 17328 KB Output is correct
11 Correct 10 ms 17236 KB Output is correct
12 Correct 9 ms 17232 KB Output is correct
13 Correct 8 ms 17236 KB Output is correct
14 Correct 8 ms 16340 KB Output is correct
15 Correct 8 ms 17236 KB Output is correct
16 Correct 7 ms 16376 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16340 KB Output is correct
2 Correct 11 ms 16404 KB Output is correct
3 Correct 8 ms 16468 KB Output is correct
4 Correct 8 ms 16468 KB Output is correct
5 Correct 15 ms 22288 KB Output is correct
6 Correct 15 ms 22252 KB Output is correct
7 Correct 16 ms 22324 KB Output is correct
8 Correct 12 ms 22228 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16336 KB Output is correct
2 Correct 9 ms 16472 KB Output is correct
3 Correct 6 ms 16468 KB Output is correct
4 Correct 7 ms 16340 KB Output is correct
5 Correct 7 ms 16468 KB Output is correct
6 Correct 6 ms 16468 KB Output is correct
7 Correct 6 ms 16468 KB Output is correct
8 Correct 7 ms 16468 KB Output is correct
9 Correct 7 ms 17236 KB Output is correct
10 Correct 8 ms 17348 KB Output is correct
11 Correct 7 ms 17228 KB Output is correct
12 Correct 8 ms 17236 KB Output is correct
13 Correct 8 ms 17236 KB Output is correct
14 Correct 14 ms 22228 KB Output is correct
15 Correct 16 ms 22228 KB Output is correct
16 Correct 17 ms 22328 KB Output is correct
17 Correct 17 ms 22192 KB Output is correct
18 Correct 18 ms 22264 KB Output is correct
19 Correct 18 ms 22356 KB Output is correct
20 Correct 19 ms 22356 KB Output is correct
21 Correct 15 ms 22272 KB Output is correct
22 Correct 16 ms 22248 KB Output is correct
23 Correct 16 ms 22292 KB Output is correct
24 Correct 16 ms 22228 KB Output is correct
25 Correct 7 ms 16340 KB Output is correct
26 Correct 8 ms 17256 KB Output is correct
27 Correct 8 ms 16316 KB Output is correct
28 Correct 12 ms 22228 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16340 KB Output is correct
2 Correct 7 ms 16464 KB Output is correct
3 Correct 7 ms 16468 KB Output is correct
4 Correct 7 ms 16340 KB Output is correct
5 Correct 7 ms 16464 KB Output is correct
6 Correct 8 ms 16468 KB Output is correct
7 Correct 7 ms 16468 KB Output is correct
8 Correct 8 ms 16468 KB Output is correct
9 Correct 8 ms 17236 KB Output is correct
10 Correct 8 ms 17232 KB Output is correct
11 Correct 9 ms 17296 KB Output is correct
12 Correct 8 ms 17312 KB Output is correct
13 Correct 8 ms 17340 KB Output is correct
14 Correct 14 ms 22192 KB Output is correct
15 Correct 16 ms 22244 KB Output is correct
16 Correct 18 ms 22228 KB Output is correct
17 Correct 14 ms 22276 KB Output is correct
18 Correct 18 ms 22356 KB Output is correct
19 Correct 18 ms 22364 KB Output is correct
20 Correct 19 ms 22356 KB Output is correct
21 Correct 14 ms 22236 KB Output is correct
22 Correct 16 ms 22176 KB Output is correct
23 Correct 15 ms 22236 KB Output is correct
24 Correct 232 ms 83696 KB Output is correct
25 Correct 405 ms 83848 KB Output is correct
26 Correct 317 ms 83640 KB Output is correct
27 Correct 296 ms 83708 KB Output is correct
28 Correct 178 ms 83308 KB Output is correct
29 Correct 197 ms 83420 KB Output is correct
30 Correct 228 ms 83348 KB Output is correct
31 Correct 17 ms 22228 KB Output is correct
32 Correct 300 ms 83512 KB Output is correct
33 Correct 7 ms 16340 KB Output is correct
34 Correct 8 ms 17236 KB Output is correct
35 Correct 221 ms 75688 KB Output is correct
36 Correct 7 ms 16340 KB Output is correct
37 Correct 13 ms 22232 KB Output is correct
38 Correct 135 ms 83396 KB Output is correct
39 Correct 148 ms 60008 KB Output is correct