oj.uz

Submission #394768

# Submission time Handle Problem Language Result Execution time Memory
394768 2021-04-27T09:56:31 Z negar_a Portals (BOI14_portals) C++14
100 / 100
 749 ms 175600 KB 
//!yrt tsuj uoy srettam gnihton no emoc
#include <bits/stdc++.h>
//#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
using namespace std;

typedef long long ll;
typedef long double ld;
#define um unordered_map
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second

int r, c;
const int N = 1e3 + 2;
pii up[N][N], dw[N][N], le[N][N], ri[N][N];
int mn[N][N], inf = 1e9 + 7; 
char s[N][N];
vector <pair <pii, int>> adj[N][N];
int h[N][N];
bool mark[N][N];
set <pair <int, pii>> q;

inline void add_edge(int i, int j){
	adj[i][j].pb({dw[i][j], mn[i][j] + 1});
	adj[i][j].pb({le[i][j], mn[i][j] + 1});
	adj[i][j].pb({ri[i][j], mn[i][j] + 1});
	adj[i][j].pb({up[i][j], mn[i][j] + 1});
}

inline void UP(){
	for(int i = 0; i < r; i ++){
		for(int j = 0; j < c; j ++){
			if(i <= 0 || s[i - 1][j] == '#'){
				up[i][j] = {i, j};
			}else{
				up[i][j] = up[i - 1][j];
			}
			mn[i][j] = min(mn[i][j], abs(i - up[i][j].F));
		}
	}
}
inline void DOWN(){
	for(int i = r - 1; i >= 0; i --){
		for(int j = 0; j < c; j ++){
			if(i >= r - 1 || s[i + 1][j] == '#'){
				dw[i][j] = {i, j};
			}else{
				dw[i][j] = dw[i + 1][j];
			}
			mn[i][j] = min(mn[i][j], abs(i - dw[i][j].F));
		}
	}
}
inline void LEFT(){
	for(int j = 0; j < c; j ++){
		for(int i = 0; i < r; i ++){
			if(j <= 0 || s[i][j - 1] == '#'){
				le[i][j] = {i, j};
			}else{
				le[i][j] = le[i][j - 1];
			}
			mn[i][j] = min(mn[i][j], abs(j - le[i][j].S));
		}
	}
}
inline void RIGHT(){
	for(int j = c - 1; j >= 0; j --){
		for(int i = 0; i < r; i ++){
			if(j >= c - 1 || s[i][j + 1] == '#'){
				ri[i][j] = {i, j};
			}else{
				ri[i][j] = ri[i][j + 1];
			}
			mn[i][j] = min(mn[i][j], abs(j - ri[i][j].S));
		}
	}
}

inline void dijk(pii v){
	q.insert({0, v});
	h[v.F][v.S] = 0;
//	mark[v.F][v.S] = true;
	while(q.size()){
		int w = q.begin() -> F;
		pii x = q.begin() -> S;
		q.erase(q.begin());
//		mark[x.F][x.S] = false;
		if(w <= h[x.F][x.S]){
			for(auto u : adj[x.F][x.S]){
				if(h[u.F.F][u.F.S] > h[x.F][x.S] + u.S){
					h[u.F.F][u.F.S] = h[x.F][x.S] + u.S;
//					if(!mark[u.F.F][u.F.S]){
//						mark[u.F.F][u.F.S] = true;
						q.insert({h[u.F.F][u.F.S], u.F});
//					}
				}
			}
		}
	}
}

int main(){
	fast_io;
	scanf("%d %d", &r, &c);
	pii st, en;
	for(int i = 0; i < r; i ++){
		scanf("%s", &s[i]);
		for(int j = 0; j < c; j ++){
			if(s[i][j] == 'S'){
				st = {i, j};
			}
			if(s[i][j] == 'C'){
				en = {i, j};
			}
			mn[i][j] = h[i][j] = inf;
		}
	}
	UP();
	DOWN();
	LEFT();
	RIGHT();
	for(int i = 0; i < r; i ++){
		for(int j = 0; j < c; j ++){
			if(i > 0 && s[i - 1][j] != '#'){
				adj[i][j].pb({{i - 1, j}, 1});
			}
			if(i < r - 1 && s[i + 1][j] != '#'){
				adj[i][j].pb({{i + 1, j}, 1});
			}
			if(j > 0 && s[i][j - 1] != '#'){
				adj[i][j].pb({{i, j - 1}, 1});
			}
			if(j < c - 1 && s[i][j + 1] != '#'){
				adj[i][j].pb({{i, j + 1}, 1});
			}
			add_edge(i, j);
		}
	}
	dijk(st);
	printf("%d", h[en.F][en.S]);
	
	return 0;
}

Compilation message

portals.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("Ofast")
      | 
portals.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      | 
portals.cpp: In function 'int main()':
portals.cpp:112:11: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1002]' [-Wformat=]
  112 |   scanf("%s", &s[i]);
      |          ~^   ~~~~~
      |           |   |
      |           |   char (*)[1002]
      |           char*
portals.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  109 |  scanf("%d %d", &r, &c);
      |  ~~~~~^~~~~~~~~~~~~~~~~
portals.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  112 |   scanf("%s", &s[i]);
      |   ~~~~~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23928 KB Output is correct
2 Correct 18 ms 24160 KB Output is correct
3 Correct 16 ms 24156 KB Output is correct
4 Correct 15 ms 23952 KB Output is correct
5 Correct 15 ms 24156 KB Output is correct
6 Correct 16 ms 24140 KB Output is correct
7 Correct 16 ms 24140 KB Output is correct
8 Correct 16 ms 24156 KB Output is correct
9 Correct 17 ms 24012 KB Output is correct
10 Correct 17 ms 24012 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23908 KB Output is correct
2 Correct 15 ms 24164 KB Output is correct
3 Correct 15 ms 24148 KB Output is correct
4 Correct 16 ms 24012 KB Output is correct
5 Correct 16 ms 24188 KB Output is correct
6 Correct 16 ms 24140 KB Output is correct
7 Correct 16 ms 24168 KB Output is correct
8 Correct 16 ms 24140 KB Output is correct
9 Correct 18 ms 25420 KB Output is correct
10 Correct 17 ms 25436 KB Output is correct
11 Correct 17 ms 25456 KB Output is correct
12 Correct 17 ms 25420 KB Output is correct
13 Correct 17 ms 25464 KB Output is correct
14 Correct 16 ms 24012 KB Output is correct
15 Correct 16 ms 25516 KB Output is correct
16 Correct 18 ms 24012 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23928 KB Output is correct
2 Correct 16 ms 24168 KB Output is correct
3 Correct 16 ms 24096 KB Output is correct
4 Correct 16 ms 24140 KB Output is correct
5 Correct 33 ms 34508 KB Output is correct
6 Correct 35 ms 34544 KB Output is correct
7 Correct 40 ms 34584 KB Output is correct
8 Correct 31 ms 34528 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23908 KB Output is correct
2 Correct 15 ms 24140 KB Output is correct
3 Correct 16 ms 24100 KB Output is correct
4 Correct 16 ms 24016 KB Output is correct
5 Correct 16 ms 24140 KB Output is correct
6 Correct 16 ms 24180 KB Output is correct
7 Correct 18 ms 24140 KB Output is correct
8 Correct 16 ms 24180 KB Output is correct
9 Correct 17 ms 25420 KB Output is correct
10 Correct 20 ms 25440 KB Output is correct
11 Correct 18 ms 25464 KB Output is correct
12 Correct 17 ms 25484 KB Output is correct
13 Correct 18 ms 25528 KB Output is correct
14 Correct 34 ms 34436 KB Output is correct
15 Correct 37 ms 34532 KB Output is correct
16 Correct 36 ms 34528 KB Output is correct
17 Correct 35 ms 34484 KB Output is correct
18 Correct 37 ms 34500 KB Output is correct
19 Correct 46 ms 34536 KB Output is correct
20 Correct 44 ms 34508 KB Output is correct
21 Correct 33 ms 34460 KB Output is correct
22 Correct 35 ms 34504 KB Output is correct
23 Correct 35 ms 34500 KB Output is correct
24 Correct 36 ms 34480 KB Output is correct
25 Correct 16 ms 24012 KB Output is correct
26 Correct 19 ms 25444 KB Output is correct
27 Correct 17 ms 24004 KB Output is correct
28 Correct 30 ms 34492 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23884 KB Output is correct
2 Correct 17 ms 24128 KB Output is correct
3 Correct 17 ms 24168 KB Output is correct
4 Correct 16 ms 24012 KB Output is correct
5 Correct 16 ms 24096 KB Output is correct
6 Correct 16 ms 24164 KB Output is correct
7 Correct 15 ms 24188 KB Output is correct
8 Correct 16 ms 24140 KB Output is correct
9 Correct 19 ms 25420 KB Output is correct
10 Correct 19 ms 25392 KB Output is correct
11 Correct 17 ms 25416 KB Output is correct
12 Correct 17 ms 25420 KB Output is correct
13 Correct 20 ms 25388 KB Output is correct
14 Correct 34 ms 34476 KB Output is correct
15 Correct 42 ms 34500 KB Output is correct
16 Correct 35 ms 34536 KB Output is correct
17 Correct 34 ms 34416 KB Output is correct
18 Correct 36 ms 34608 KB Output is correct
19 Correct 39 ms 34620 KB Output is correct
20 Correct 42 ms 34504 KB Output is correct
21 Correct 33 ms 34516 KB Output is correct
22 Correct 35 ms 34544 KB Output is correct
23 Correct 35 ms 34548 KB Output is correct
24 Correct 544 ms 173744 KB Output is correct
25 Correct 749 ms 175600 KB Output is correct
26 Correct 645 ms 174892 KB Output is correct
27 Correct 624 ms 175112 KB Output is correct
28 Correct 450 ms 174140 KB Output is correct
29 Correct 482 ms 174464 KB Output is correct
30 Correct 529 ms 174436 KB Output is correct
31 Correct 37 ms 34628 KB Output is correct
32 Correct 654 ms 174692 KB Output is correct
33 Correct 16 ms 24012 KB Output is correct
34 Correct 20 ms 25420 KB Output is correct
35 Correct 606 ms 174808 KB Output is correct
36 Correct 15 ms 24012 KB Output is correct
37 Correct 31 ms 34548 KB Output is correct
38 Correct 398 ms 174652 KB Output is correct
39 Correct 493 ms 174592 KB Output is correct