oj.uz

Submission #394781

# Submission time Handle Problem Language Result Execution time Memory
394781 2021-04-27T10:09:42 Z Nima_Naderi Portals (BOI14_portals) C++14
100 / 100
 768 ms 219004 KB 
//In the name of GOD
#include<bits/stdc++.h>
using namespace std;

//typedef long long ll;
typedef int ll;
const ll MXN = 1e6 + 5;
const ll MXK = 1e3 + 5;
const ll INF = 1e9;
ll n, m;
ll gin[MXN], Q[MXN], dis[MXN], nxt[4][MXN];
string s[MXK];
vector<ll> adj[MXN], lvl[MXN];
vector<pair<ll, ll>> G[MXN];
vector<pair<ll, ll>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
bool wall[4][MXN], vis[MXN];
inline ll Id(ll i, ll j){
	return i * m + j + 1;
}
inline bool check(ll x, ll y){
	return (0 <= x && x < n && 0 <= y && y < m);
}
void BFS0(){
	ll L = 0, R = -1;
	for(int i = 1; i <= n * m; i ++){
		if(!gin[i]) vis[i] = 1, Q[++ R] = i;
	}
	while(L < R){
		ll u = Q[L ++];
		for(auto v : adj[u]){
			if(!vis[v]){
				gin[v] = gin[u] + 1;
				Q[++ R] = v; vis[v] = 1;
			}
		}
	}
}
ll DIJ(ll src, ll snk){
	memset(vis, 0, sizeof vis);
	memset(dis, 31, sizeof dis);
	dis[src] = 0; lvl[0].push_back(src);
	for(int d = 0; d < MXN; d ++){
		for(auto u : lvl[d]){
			if(vis[u]) continue;
			if(u == snk) return d;
			vis[u] = 1;
			for(auto Pr : G[u]){
				ll v, w; tie(v, w) = Pr;
				if(!vis[v] && w + d < dis[v]){
					dis[v] = w + d;
					lvl[dis[v]].push_back(v);
				}
			}	
		}
	}
	return -1;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	cin >> n >> m; ll src, snk;
	for(int i = 0; i < n; i ++) cin >> s[i];
	for(int i = 0; i < n; i ++){
		for(int j = 0; j < m; j ++){
			ll u = Id(i, j); gin[u] = INF;
			if(s[i][j] == '#') continue;
			if(s[i][j] == 'S') src = Id(i, j);
			if(s[i][j] == 'C') snk = Id(i, j);
			for(int d = 0; d < 4; d ++){
				ll ip = i + dir[d].first, jp = j + dir[d].second;
				if(!check(ip, jp) || s[ip][jp] == '#') wall[d][u] = 1, gin[u] = 0;
				else adj[u].push_back(Id(ip, jp));	
			}
		}
	}
	for(int i = 0; i < n; i ++){
		for(int j = 0; j < m; j ++){
			if(s[i][j] == '#') continue;
			ll u = Id(i, j);
			nxt[2][u] = (wall[2][u] ? u : nxt[2][Id(i, j - 1)]);
		}
		for(int j = m - 1; ~j; j --){
			if(s[i][j] == '#') continue;
			ll u = Id(i, j);
			nxt[0][u] = (wall[0][u] ? u : nxt[0][Id(i, j + 1)]);
		}
	}
	for(int j = 0; j < m; j ++){
		for(int i = 0; i < n; i ++){
			if(s[i][j] == '#') continue;
			ll u = Id(i, j);
			nxt[3][u] = (wall[3][u] ? u : nxt[3][Id(i - 1, j)]);
		}
		for(int i = n - 1; ~i; i --){
			if(s[i][j] == '#') continue;
			ll u = Id(i, j);
			nxt[1][u] = (wall[1][u] ? u : nxt[1][Id(i + 1, j)]);
		}
	}
	BFS0();
	for(int i = 0; i < n; i ++){
		for(int j = 0; j < m; j ++){
			ll u = Id(i, j), v;
			for(int d = 0; d < 4; d  ++){
				v = nxt[d][u];
				if(v != u && v != Id(i + dir[d].first, j + dir[d].second)) G[u].push_back({v, gin[u] + 1});
			}
			for(auto v : adj[u]){
				G[u].push_back({v, 1});
			}
		}
	}
	cout << DIJ(src, snk) << '\n';
	return 0;
}
// N.N_2004
// THIS IS THE PAYOFF

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:112:27: warning: 'src' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |  cout << DIJ(src, snk) << '\n';
      |                           ^~~~
portals.cpp:112:27: warning: 'snk' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 75712 KB Output is correct
2 Correct 76 ms 75660 KB Output is correct
3 Correct 47 ms 75760 KB Output is correct
4 Correct 48 ms 75720 KB Output is correct
5 Correct 52 ms 75672 KB Output is correct
6 Correct 52 ms 75760 KB Output is correct
7 Correct 47 ms 75736 KB Output is correct
8 Correct 52 ms 75712 KB Output is correct
9 Correct 51 ms 75656 KB Output is correct
10 Correct 47 ms 75688 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 75708 KB Output is correct
2 Correct 56 ms 75624 KB Output is correct
3 Correct 52 ms 75756 KB Output is correct
4 Correct 56 ms 75740 KB Output is correct
5 Correct 51 ms 75748 KB Output is correct
6 Correct 65 ms 75716 KB Output is correct
7 Correct 52 ms 75728 KB Output is correct
8 Correct 52 ms 75672 KB Output is correct
9 Correct 54 ms 76040 KB Output is correct
10 Correct 52 ms 76076 KB Output is correct
11 Correct 53 ms 76040 KB Output is correct
12 Correct 56 ms 76116 KB Output is correct
13 Correct 50 ms 76012 KB Output is correct
14 Correct 53 ms 75748 KB Output is correct
15 Correct 52 ms 76044 KB Output is correct
16 Correct 52 ms 75664 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 75664 KB Output is correct
2 Correct 62 ms 75644 KB Output is correct
3 Correct 48 ms 75744 KB Output is correct
4 Correct 52 ms 75736 KB Output is correct
5 Correct 64 ms 79488 KB Output is correct
6 Correct 75 ms 79588 KB Output is correct
7 Correct 61 ms 79704 KB Output is correct
8 Correct 52 ms 80004 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 75732 KB Output is correct
2 Correct 44 ms 75692 KB Output is correct
3 Correct 53 ms 75716 KB Output is correct
4 Correct 51 ms 75712 KB Output is correct
5 Correct 63 ms 75696 KB Output is correct
6 Correct 59 ms 75680 KB Output is correct
7 Correct 50 ms 75728 KB Output is correct
8 Correct 45 ms 75684 KB Output is correct
9 Correct 51 ms 76096 KB Output is correct
10 Correct 50 ms 76096 KB Output is correct
11 Correct 52 ms 75964 KB Output is correct
12 Correct 54 ms 75900 KB Output is correct
13 Correct 49 ms 75952 KB Output is correct
14 Correct 63 ms 79452 KB Output is correct
15 Correct 86 ms 79536 KB Output is correct
16 Correct 91 ms 79724 KB Output is correct
17 Correct 65 ms 80020 KB Output is correct
18 Correct 101 ms 80504 KB Output is correct
19 Correct 72 ms 81276 KB Output is correct
20 Correct 67 ms 81348 KB Output is correct
21 Correct 63 ms 79508 KB Output is correct
22 Correct 62 ms 79464 KB Output is correct
23 Correct 63 ms 79568 KB Output is correct
24 Correct 71 ms 81428 KB Output is correct
25 Correct 48 ms 75712 KB Output is correct
26 Correct 49 ms 75984 KB Output is correct
27 Correct 49 ms 75644 KB Output is correct
28 Correct 63 ms 79892 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 75668 KB Output is correct
2 Correct 50 ms 75632 KB Output is correct
3 Correct 49 ms 75748 KB Output is correct
4 Correct 48 ms 75680 KB Output is correct
5 Correct 46 ms 75648 KB Output is correct
6 Correct 47 ms 75696 KB Output is correct
7 Correct 48 ms 75708 KB Output is correct
8 Correct 47 ms 75756 KB Output is correct
9 Correct 48 ms 76080 KB Output is correct
10 Correct 48 ms 76040 KB Output is correct
11 Correct 49 ms 75892 KB Output is correct
12 Correct 48 ms 75980 KB Output is correct
13 Correct 49 ms 75972 KB Output is correct
14 Correct 62 ms 79448 KB Output is correct
15 Correct 82 ms 79556 KB Output is correct
16 Correct 64 ms 79764 KB Output is correct
17 Correct 67 ms 80108 KB Output is correct
18 Correct 68 ms 80580 KB Output is correct
19 Correct 78 ms 81196 KB Output is correct
20 Correct 66 ms 81348 KB Output is correct
21 Correct 62 ms 79556 KB Output is correct
22 Correct 64 ms 79448 KB Output is correct
23 Correct 64 ms 79636 KB Output is correct
24 Correct 492 ms 188100 KB Output is correct
25 Correct 768 ms 217100 KB Output is correct
26 Correct 554 ms 212532 KB Output is correct
27 Correct 623 ms 214656 KB Output is correct
28 Correct 458 ms 169996 KB Output is correct
29 Correct 467 ms 169616 KB Output is correct
30 Correct 464 ms 170128 KB Output is correct
31 Correct 70 ms 81576 KB Output is correct
32 Correct 678 ms 219004 KB Output is correct
33 Correct 48 ms 75716 KB Output is correct
34 Correct 47 ms 75976 KB Output is correct
35 Correct 504 ms 191904 KB Output is correct
36 Correct 49 ms 75724 KB Output is correct
37 Correct 60 ms 79940 KB Output is correct
38 Correct 417 ms 181428 KB Output is correct
39 Correct 350 ms 166732 KB Output is correct