oj.uz

Submission #235447

# Submission time Handle Problem Language Result Execution time Memory
235447 2020-05-28T10:02:40 Z Atalasion Portals (BOI14_portals) C++14
100 / 100
 803 ms 144812 KB 
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize ("Ofast")
#pragma GCC optimize("unroll-loops")


using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 1000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;

char grid[N][N];
int dis[N][N], n, m, near[N][N];
int a[] = {0, 0, 1, -1};
int b[] = {1, -1, 0, 0};
vector<pair<pii, int>> G[N][N];
vi sat[N], sot[N];

bool isval(int x, int y){
	return (x > 0 && x <= n && y > 0 && y <= m && grid[x][y] != '#');
}

void BFS(){
	memset(near, 31, sizeof near);
	queue<pii> q;
	for (int i = 0; i <= n + 1; i++) for (int j = 0; j <= m + 1; j++){
		if (grid[i][j] == '#') near[i][j] = 0, q.push({i, j});
	}
	while (q.size()){
		pii fr = q.front();
		q.pop();
		for (int i = 0; i < 4; i++){
			if (isval(fr.F + a[i], fr.S + b[i])){
				int x = fr.F + a[i], y = fr.S + b[i];
				if (near[x][y] > near[fr.F][fr.S] + 1){
					near[x][y] = near[fr.F][fr.S] + 1;
					q.push({x, y});
				}
			}
		}
	}
}

void DJ(int x, int y){
	memset(dis, 31, sizeof dis);
	dis[x][y] = 0;
	set<pair<int, pii>> st;
	st.insert({0, {x, y}});
	while (st.size()){
		pair<int, pii> fr = *st.begin();
		st.erase(st.begin());
		for (auto u:G[fr.S.F][fr.S.S]){
			if (dis[u.F.F][u.F.S] > fr.F + u.S){
				st.erase({dis[u.F.F][u.F.S], {u.F.F, u.F.S}});
				dis[u.F.F][u.F.S] = fr.F + u.S;
				st.insert({dis[u.F.F][u.F.S], {u.F.F, u.F.S}});
			}
		}
	}
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	int s1, s2, f1, f2;
	for (int i = 0; i <= m + 1; i++) grid[0][i] = '#', grid[n + 1][i] = '#';
	for (int i = 0; i <= n + 1; i++) grid[i][0] = '#', grid[i][m + 1] = '#';
	for (int i = 1; i <= m; i++) sot[i].pb(0), sot[i].pb(n + 1);
	for( int i = 1; i <= n; i++)sat[i].pb(0), sat[i].pb(m + 1);
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			cin >> grid[i][j];
			if (grid[i][j] == '#'){
				sat[i].pb(j);
				sot[j].pb(i);
			}
			if (grid[i][j] == 'S') s1 = i, s2 = j;
			if (grid[i][j] == 'C') f1 = i, f2 = j;
		}
	} 
	for (int i = 1; i <= n; i++) sort(all(sat[i]));
	for (int i = 1; i <= m; i++) sort(all(sot[i]));
	BFS();
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++){
		if (grid[i][j] != '#'){
			for (int k = 0; k < 4; k++){
				if (isval(i + a[k], j + b[k])){
					G[i][j].pb({{i + a[k], j + b[k]}, 1});
				}
			}
			int x = lower_bound(all(sat[i]), j) - sat[i].begin();
			G[i][j].pb({{i, sat[i][x] - 1}, near[i][j]});
			G[i][j].pb({{i, sat[i][x - 1] + 1}, near[i][j]});
			x = lower_bound(all(sot[j]), i) - sot[j].begin();
			G[i][j].pb({{sot[j][x] - 1, j}, near[i][j]});
			G[i][j].pb({{sot[j][x - 1] + 1, j}, near[i][j]});
		}
	}
	DJ(s1, s2);
	cout << dis[f1][f2];








	return 0;
}

Compilation message

portals.cpp: In function 'int32_t main()':
portals.cpp:110:4: warning: 's2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  DJ(s1, s2);
  ~~^~~~~~~~
portals.cpp:111:20: warning: 'f1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout << dis[f1][f2];
                    ^
portals.cpp:111:20: warning: 'f2' may be used uninitialized in this function [-Wmaybe-uninitialized]
portals.cpp:110:4: warning: 's1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  DJ(s1, s2);
  ~~^~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 32256 KB Output is correct
2 Correct 23 ms 32384 KB Output is correct
3 Correct 23 ms 32384 KB Output is correct
4 Correct 23 ms 32512 KB Output is correct
5 Correct 23 ms 32384 KB Output is correct
6 Correct 25 ms 32384 KB Output is correct
7 Correct 24 ms 32384 KB Output is correct
8 Correct 23 ms 32384 KB Output is correct
9 Correct 23 ms 32384 KB Output is correct
10 Correct 22 ms 32384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 32384 KB Output is correct
2 Correct 24 ms 32384 KB Output is correct
3 Correct 23 ms 32384 KB Output is correct
4 Correct 23 ms 32384 KB Output is correct
5 Correct 23 ms 32384 KB Output is correct
6 Correct 23 ms 32384 KB Output is correct
7 Correct 23 ms 32384 KB Output is correct
8 Correct 23 ms 32384 KB Output is correct
9 Correct 24 ms 32640 KB Output is correct
10 Correct 24 ms 32640 KB Output is correct
11 Correct 24 ms 32512 KB Output is correct
12 Correct 24 ms 32512 KB Output is correct
13 Correct 25 ms 32640 KB Output is correct
14 Correct 23 ms 32384 KB Output is correct
15 Correct 24 ms 32640 KB Output is correct
16 Correct 25 ms 32384 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 32256 KB Output is correct
2 Correct 22 ms 32384 KB Output is correct
3 Correct 24 ms 32512 KB Output is correct
4 Correct 23 ms 32384 KB Output is correct
5 Correct 38 ms 35248 KB Output is correct
6 Correct 41 ms 35372 KB Output is correct
7 Correct 42 ms 35612 KB Output is correct
8 Correct 48 ms 35736 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 32384 KB Output is correct
2 Correct 24 ms 32384 KB Output is correct
3 Correct 23 ms 32376 KB Output is correct
4 Correct 23 ms 32384 KB Output is correct
5 Correct 23 ms 32384 KB Output is correct
6 Correct 23 ms 32384 KB Output is correct
7 Correct 23 ms 32384 KB Output is correct
8 Correct 23 ms 32384 KB Output is correct
9 Correct 24 ms 32640 KB Output is correct
10 Correct 24 ms 32632 KB Output is correct
11 Correct 23 ms 32512 KB Output is correct
12 Correct 24 ms 32504 KB Output is correct
13 Correct 25 ms 32640 KB Output is correct
14 Correct 39 ms 35248 KB Output is correct
15 Correct 41 ms 35380 KB Output is correct
16 Correct 43 ms 35612 KB Output is correct
17 Correct 40 ms 35552 KB Output is correct
18 Correct 46 ms 36188 KB Output is correct
19 Correct 45 ms 36984 KB Output is correct
20 Correct 44 ms 36984 KB Output is correct
21 Correct 39 ms 35384 KB Output is correct
22 Correct 41 ms 35376 KB Output is correct
23 Correct 41 ms 35508 KB Output is correct
24 Correct 46 ms 36992 KB Output is correct
25 Correct 23 ms 32384 KB Output is correct
26 Correct 24 ms 32640 KB Output is correct
27 Correct 23 ms 32384 KB Output is correct
28 Correct 36 ms 35736 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 32256 KB Output is correct
2 Correct 23 ms 32384 KB Output is correct
3 Correct 23 ms 32384 KB Output is correct
4 Correct 23 ms 32288 KB Output is correct
5 Correct 23 ms 32512 KB Output is correct
6 Correct 23 ms 32384 KB Output is correct
7 Correct 23 ms 32384 KB Output is correct
8 Correct 23 ms 32376 KB Output is correct
9 Correct 25 ms 32640 KB Output is correct
10 Correct 25 ms 32640 KB Output is correct
11 Correct 24 ms 32640 KB Output is correct
12 Correct 24 ms 32512 KB Output is correct
13 Correct 24 ms 32640 KB Output is correct
14 Correct 39 ms 35256 KB Output is correct
15 Correct 41 ms 35372 KB Output is correct
16 Correct 42 ms 35684 KB Output is correct
17 Correct 41 ms 35672 KB Output is correct
18 Correct 45 ms 36180 KB Output is correct
19 Correct 46 ms 36984 KB Output is correct
20 Correct 46 ms 36984 KB Output is correct
21 Correct 40 ms 35376 KB Output is correct
22 Correct 40 ms 35384 KB Output is correct
23 Correct 41 ms 35500 KB Output is correct
24 Correct 538 ms 112884 KB Output is correct
25 Correct 803 ms 144812 KB Output is correct
26 Correct 680 ms 144376 KB Output is correct
27 Correct 691 ms 144276 KB Output is correct
28 Correct 449 ms 101160 KB Output is correct
29 Correct 483 ms 102740 KB Output is correct
30 Correct 532 ms 104100 KB Output is correct
31 Correct 44 ms 36984 KB Output is correct
32 Correct 673 ms 144024 KB Output is correct
33 Correct 23 ms 32384 KB Output is correct
34 Correct 24 ms 32640 KB Output is correct
35 Correct 530 ms 118712 KB Output is correct
36 Correct 23 ms 32384 KB Output is correct
37 Correct 36 ms 35736 KB Output is correct
38 Correct 391 ms 111616 KB Output is correct
39 Correct 361 ms 93512 KB Output is correct