oj.uz

Submission #1097647

# Submission time Handle Problem Language Result Execution time Memory
1097647 2024-10-07T19:17:19 Z vako_p Portals (BOI14_portals) C++14
100 / 100
 487 ms 190032 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define pb push_back

const int mxN = 2e6 + 5, mxN1 = 2005;
ll n,m,dis[mxN],dis1[mxN],st,fi,idx[mxN1][mxN1];
pair<ll,ll> wall[mxN][5];
char a[mxN1][mxN1];
bool vis[mxN];
vector<pair<ll,ll>> v[mxN];
queue<ll> qq;
priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> q;

void bfs(){
	while(!qq.empty()){
		ll at = qq.front(); qq.pop();
		for(auto it1 : v[at]){
			ll it = it1.first;
			if(vis[it]) continue;
			dis1[it] = dis1[at] + 1;
			vis[it] = true;
			qq.push(it);
		}
	}
}

void f(){
	for(int i = 0; i <= n + 1; i++){
		for(int j = 0; j <= m + 1; j++){
			if(a[i][j] == '#'){
				wall[idx[i][j]][0] = make_pair(i, j + 1);
				wall[idx[i][j]][1] = make_pair(i + 1, j);
			}	
			else{
				wall[idx[i][j]][0] = wall[idx[i][j - 1]][0];
				wall[idx[i][j]][1] = wall[idx[i - 1][j]][1];
			} 
		}	
	}
	for(int i = n + 1; i >= 0; i--){
		for(int j = m + 1; j >= 0; j--){
			if(a[i][j] == '#'){
				wall[idx[i][j]][2] = make_pair(i, j - 1);
				wall[idx[i][j]][3] = make_pair(i - 1, j);
			}
			else{
				wall[idx[i][j]][2] = wall[idx[i][j + 1]][2];
				wall[idx[i][j]][3] = wall[idx[i + 1][j]][3];
			}
			if(a[i][j] == '#') continue;
			for(int k = 0; k < 4; k++){
				pair<ll,ll> x = wall[idx[i][j]][k];
				if(abs(x.first - i) + abs(x.second - j) > dis1[idx[i][j]]){
					v[idx[i][j]].pb({x.first * (m + 2) + x.second, dis1[idx[i][j]]});
				}
			}
		}
	}
}

void dijkstra(){
	for(int i = 1; i < mxN; i++){
		dis[i] = 1e9;
		vis[i] = false;
	}
	q.push({0, st});
	dis[st] = 0;
	while(!q.empty()){
		ll at = q.top().second; q.pop();
		if(vis[at]) continue;
		vis[at] = true;
//		cout << at / (m + 2) << ' ' << at % (m + 2) << ' ' << dis[at] << ' ' << '\n';
		for(auto it : v[at]){
			if(vis[it.first]) continue;
			if(dis[it.first] > dis[at] + it.second){
				dis[it.first] = dis[at] + it.second;
				q.push({dis[it.first], it.first});
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i = 0; i <= n + 1; i++){
		for(int j = 0; j <= m + 1; j++){
			if(i == 0 or i == n + 1 or j == 0 or j == m + 1) a[i][j] = '#';
			else cin >> a[i][j];
			idx[i][j] = i * (m + 2) + j;
			if(a[i][j] == '#') qq.push(idx[i][j]);
			if(a[i][j] == 'S'){
				st = idx[i][j];
				a[i][j] = '.';
			}
			if(a[i][j] == 'C'){
				fi = idx[i][j];
				a[i][j] = '.';
			}
		}
	}
	for(int i = 0; i <= n + 1; i++){
		for(int j = 0; j <= m + 1; j++){
			if(i > 0 and a[i - 1][j] != '#') v[idx[i][j]].pb({idx[i - 1][j], 1});
			if(i < n + 1 and a[i + 1][j] != '#') v[idx[i][j]].pb({idx[i + 1][j], 1});
			if(j > 0 and a[i][j - 1] != '#') v[idx[i][j]].pb({idx[i][j - 1], 1});
			if(j < m + 1 and a[i][j + 1] != '#') v[idx[i][j]].pb({idx[i][j + 1], 1});  
		}
	}
 	bfs();
 	f();
 	dijkstra(); 
 	cout << dis[fi]; 
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 57180 KB Output is correct
2 Correct 27 ms 57180 KB Output is correct
3 Correct 27 ms 57312 KB Output is correct
4 Correct 38 ms 57240 KB Output is correct
5 Correct 27 ms 57176 KB Output is correct
6 Correct 41 ms 57060 KB Output is correct
7 Correct 27 ms 57176 KB Output is correct
8 Correct 27 ms 57432 KB Output is correct
9 Correct 26 ms 57180 KB Output is correct
10 Correct 26 ms 57180 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 57180 KB Output is correct
2 Correct 25 ms 57180 KB Output is correct
3 Correct 32 ms 57216 KB Output is correct
4 Correct 26 ms 57172 KB Output is correct
5 Correct 26 ms 57168 KB Output is correct
6 Correct 26 ms 57172 KB Output is correct
7 Correct 26 ms 57180 KB Output is correct
8 Correct 40 ms 57172 KB Output is correct
9 Correct 27 ms 57684 KB Output is correct
10 Correct 27 ms 57756 KB Output is correct
11 Correct 29 ms 57692 KB Output is correct
12 Correct 34 ms 57644 KB Output is correct
13 Correct 26 ms 57856 KB Output is correct
14 Correct 26 ms 57176 KB Output is correct
15 Correct 30 ms 57692 KB Output is correct
16 Correct 28 ms 57168 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 57176 KB Output is correct
2 Correct 26 ms 57220 KB Output is correct
3 Correct 27 ms 57180 KB Output is correct
4 Correct 42 ms 57172 KB Output is correct
5 Correct 40 ms 62312 KB Output is correct
6 Correct 46 ms 62296 KB Output is correct
7 Correct 36 ms 62556 KB Output is correct
8 Correct 32 ms 61788 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 57168 KB Output is correct
2 Correct 40 ms 57180 KB Output is correct
3 Correct 26 ms 57080 KB Output is correct
4 Correct 26 ms 57172 KB Output is correct
5 Correct 26 ms 57156 KB Output is correct
6 Correct 31 ms 57180 KB Output is correct
7 Correct 33 ms 57280 KB Output is correct
8 Correct 40 ms 57168 KB Output is correct
9 Correct 33 ms 57692 KB Output is correct
10 Correct 27 ms 57660 KB Output is correct
11 Correct 42 ms 57632 KB Output is correct
12 Correct 28 ms 57692 KB Output is correct
13 Correct 40 ms 57684 KB Output is correct
14 Correct 34 ms 62216 KB Output is correct
15 Correct 35 ms 62296 KB Output is correct
16 Correct 37 ms 62548 KB Output is correct
17 Correct 35 ms 62548 KB Output is correct
18 Correct 39 ms 63060 KB Output is correct
19 Correct 38 ms 63572 KB Output is correct
20 Correct 40 ms 63392 KB Output is correct
21 Correct 34 ms 62228 KB Output is correct
22 Correct 53 ms 62292 KB Output is correct
23 Correct 34 ms 62288 KB Output is correct
24 Correct 40 ms 63312 KB Output is correct
25 Correct 26 ms 57180 KB Output is correct
26 Correct 42 ms 57692 KB Output is correct
27 Correct 26 ms 57180 KB Output is correct
28 Correct 49 ms 61780 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 57180 KB Output is correct
2 Correct 27 ms 57180 KB Output is correct
3 Correct 24 ms 57172 KB Output is correct
4 Correct 40 ms 57256 KB Output is correct
5 Correct 31 ms 57180 KB Output is correct
6 Correct 27 ms 57172 KB Output is correct
7 Correct 27 ms 57272 KB Output is correct
8 Correct 39 ms 57052 KB Output is correct
9 Correct 40 ms 57680 KB Output is correct
10 Correct 27 ms 57692 KB Output is correct
11 Correct 26 ms 57688 KB Output is correct
12 Correct 41 ms 57596 KB Output is correct
13 Correct 28 ms 57692 KB Output is correct
14 Correct 34 ms 62284 KB Output is correct
15 Correct 35 ms 62288 KB Output is correct
16 Correct 37 ms 62544 KB Output is correct
17 Correct 35 ms 62548 KB Output is correct
18 Correct 48 ms 63056 KB Output is correct
19 Correct 42 ms 63568 KB Output is correct
20 Correct 61 ms 63568 KB Output is correct
21 Correct 34 ms 62288 KB Output is correct
22 Correct 34 ms 62300 KB Output is correct
23 Correct 40 ms 62432 KB Output is correct
24 Correct 346 ms 172452 KB Output is correct
25 Correct 471 ms 190032 KB Output is correct
26 Correct 459 ms 189892 KB Output is correct
27 Correct 487 ms 189832 KB Output is correct
28 Correct 244 ms 158684 KB Output is correct
29 Correct 264 ms 159664 KB Output is correct
30 Correct 291 ms 160852 KB Output is correct
31 Correct 36 ms 63320 KB Output is correct
32 Correct 412 ms 189524 KB Output is correct
33 Correct 23 ms 57180 KB Output is correct
34 Correct 24 ms 57692 KB Output is correct
35 Correct 316 ms 170128 KB Output is correct
36 Correct 26 ms 57468 KB Output is correct
37 Correct 34 ms 61780 KB Output is correct
38 Correct 238 ms 149648 KB Output is correct
39 Correct 265 ms 150356 KB Output is correct