oj.uz

Submission #466817

# Submission time Handle Problem Language Result Execution time Memory
466817 2021-08-20T18:05:23 Z M4mou Portals (BOI14_portals) C++17
100 / 100
 682 ms 65748 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define inf 1000000000
#define sz(x) (ll)x.size()
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
typedef long long ll;
typedef unsigned long long ull;
typedef  double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair< int , pii> piii;
typedef pair<int,bool> pib;
typedef vector<pii> vii;
typedef vector<pib> vib;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef pair<string,string> pss;
typedef vector<pss> vss;
typedef pair<ld , ld> pdd;
typedef vector<ld> vd;
typedef vector<vector<pib>> vvib;
typedef vector<piii> viii;
typedef vector<viii> vviii;
typedef vector<bool> vb;
typedef pair<pii , bool> piib;
typedef vector<pair<pii , bool>> viib;
const int MOD = 1e9 + 7; //998244353;
 
	
struct comp
{
    bool operator()(const vi &a, const vi &b) 
{
    
    return a[0] > b[0];
}
};
 
int dirs[4][2] {{-1 , 0} , {0 , -1} , {1, 0} , {0 , 1}};
string grid[1005];
vector<set<int>> cols;
vector<set<int>> rows;
bool v[1005][1005];
int distances[1005][1005];
int closestWall[1005][1005];
int n , m;
void preprocess(){
	memset(closestWall , -1 , sizeof closestWall);
	queue<piii> bfs;
	for(int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			if(grid[i][j] == '#'){
				bfs.push({0 , {i , j}});
				closestWall[i][j] = 0;
			}
		}
	}
	while(bfs.size()){
		piii p = bfs.front();
		int dis = p.fi;
		int x = p.se.fi;
		int y = p.se.se;
		for(int i = 0;i<4;i++){
			int x0 = x + dirs[i][0];
			int y0 = y + dirs[i][1];
			if(x0 == -1 || y0 == -1 || x0 == n || y0 == m || closestWall[x0][y0] != -1)continue;
			closestWall[x0][y0] = dis + 1;
			bfs.push({dis + 1 , {x0 , y0}});
		}
		bfs.pop();
	}
}
 
vi getWalls(int x , int y){
	auto pdown = rows[y].upper_bound(x);
	int down = *pdown;
	pdown--;
	int up = *pdown;
 
	auto pright = cols[x].upper_bound(y);
	int right = *pright;
	pright--;
	int left = *pright;
	//cout << "WALLS" << up << " " << right << " " << down << " " << left << endl;
	vi walls{up+1, y , x,right-1 , down-1 , y , x, left+1};
	return walls;
}
int main(){
	// freopen("input.txt" , "r" , stdin);
	// freopen("output.txt" , "w" , stdout);
	cin >> n >> m;
	memset(v , 0 , sizeof v);
	for(int i = 1;i<=n;i++){
		cin >> grid[i];
		grid[i] = "#" + grid[i] + "#";
	}
	grid[0] = grid[n+1] = string(m+2 , '#');
	n += 2;
	m += 2;
	priority_queue<vi , vector<vi> , comp> pq;
	int initx , inity , destX , destY;
	cols.resize(n);
	rows.resize(m);
 
	for(int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			distances[i][j] = inf;
			if(grid[i][j] == 'S'){
				initx = i;
				inity = j;
				distances[i][j] = 0;
			}
			else if(grid[i][j] == 'C'){
				destX = i;
				destY = j;
			}
			else if(grid[i][j] == '#'){
				cols[i].insert(j);
				rows[j].insert(i);
			}
		}
	}
	preprocess();
	/*for(int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			cout << closestWall[i][j] << " ";  
		}
		cout << endl;
	}*/
	vi initState{0 , initx , inity};
	pq.push(initState);
	while(pq.size()){
		vi s = pq.top();
		int dis = s[0] , x = s[1] , y = s[2];
		pq.pop();
		if(v[x][y])continue;
		v[x][y] = 1;
		//cout << dis << " " << x << " " << y << endl;
		if(x == destX && y == destY){
			cout << dis << endl;
			return 0;
		}
		for(int i = 0;i<4;i++){
			int x0 = x + dirs[i][0];
			int y0 = y + dirs[i][1];
			if(grid[x0][y0] == '#' || distances[x0][y0] <= dis + 1) continue;
			distances[x0][y0] = dis + 1;
			pq.push(vi{dis + 1 , x0 , y0});
		}
		vi walls = getWalls(x , y);
		int c = closestWall[x][y];
		for(int i = 0;i<8;i+=2){
			int x0 = walls[i];
			int y0 = walls[i+1];
			int dis0 = dis + c;
			if(distances[x0][y0] <= dis0)continue;
			distances[x0][y0] = dis0;
			pq.push(vi{dis0 , x0,y0});
			//cout << "queued: "  << x0 << " " << y0 << " " <<dis0 << endl;
		}
	}
}
//NEVER GIVE UP
//LONG LONG

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:147:22: warning: 'destY' may be used uninitialized in this function [-Wmaybe-uninitialized]
  147 |   if(x == destX && y == destY){
      |                    ~~^~~~~~~~
portals.cpp:147:8: warning: 'destX' may be used uninitialized in this function [-Wmaybe-uninitialized]
  147 |   if(x == destX && y == destY){
      |      ~~^~~~~~~~
portals.cpp:138:32: warning: 'inity' may be used uninitialized in this function [-Wmaybe-uninitialized]
  138 |  vi initState{0 , initx , inity};
      |                                ^
portals.cpp:138:32: warning: 'initx' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 2 ms 5196 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 3 ms 5196 KB Output is correct
5 Correct 3 ms 5324 KB Output is correct
6 Correct 3 ms 5196 KB Output is correct
7 Correct 3 ms 5324 KB Output is correct
8 Correct 3 ms 5332 KB Output is correct
9 Correct 3 ms 5196 KB Output is correct
10 Correct 3 ms 5196 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 2 ms 5196 KB Output is correct
5 Correct 3 ms 5324 KB Output is correct
6 Correct 3 ms 5324 KB Output is correct
7 Correct 2 ms 5324 KB Output is correct
8 Correct 3 ms 5324 KB Output is correct
9 Correct 4 ms 5580 KB Output is correct
10 Correct 4 ms 5452 KB Output is correct
11 Correct 4 ms 5576 KB Output is correct
12 Correct 4 ms 5580 KB Output is correct
13 Correct 4 ms 5580 KB Output is correct
14 Correct 3 ms 5196 KB Output is correct
15 Correct 3 ms 5580 KB Output is correct
16 Correct 3 ms 5196 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 2 ms 5196 KB Output is correct
3 Correct 2 ms 5324 KB Output is correct
4 Correct 3 ms 5324 KB Output is correct
5 Correct 20 ms 8124 KB Output is correct
6 Correct 21 ms 8012 KB Output is correct
7 Correct 17 ms 7864 KB Output is correct
8 Correct 15 ms 7780 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 3 ms 5196 KB Output is correct
5 Correct 3 ms 5324 KB Output is correct
6 Correct 3 ms 5324 KB Output is correct
7 Correct 3 ms 5324 KB Output is correct
8 Correct 3 ms 5320 KB Output is correct
9 Correct 4 ms 5452 KB Output is correct
10 Correct 3 ms 5452 KB Output is correct
11 Correct 4 ms 5580 KB Output is correct
12 Correct 4 ms 5580 KB Output is correct
13 Correct 4 ms 5580 KB Output is correct
14 Correct 20 ms 8160 KB Output is correct
15 Correct 21 ms 8012 KB Output is correct
16 Correct 17 ms 7884 KB Output is correct
17 Correct 18 ms 7884 KB Output is correct
18 Correct 18 ms 7244 KB Output is correct
19 Correct 6 ms 6220 KB Output is correct
20 Correct 13 ms 6356 KB Output is correct
21 Correct 19 ms 8012 KB Output is correct
22 Correct 20 ms 8104 KB Output is correct
23 Correct 20 ms 7964 KB Output is correct
24 Correct 16 ms 6348 KB Output is correct
25 Correct 3 ms 5196 KB Output is correct
26 Correct 3 ms 5580 KB Output is correct
27 Correct 3 ms 5196 KB Output is correct
28 Correct 15 ms 7764 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 2 ms 5196 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 3 ms 5196 KB Output is correct
5 Correct 3 ms 5324 KB Output is correct
6 Correct 3 ms 5324 KB Output is correct
7 Correct 4 ms 5432 KB Output is correct
8 Correct 3 ms 5324 KB Output is correct
9 Correct 4 ms 5452 KB Output is correct
10 Correct 3 ms 5452 KB Output is correct
11 Correct 3 ms 5584 KB Output is correct
12 Correct 4 ms 5580 KB Output is correct
13 Correct 4 ms 5580 KB Output is correct
14 Correct 22 ms 8140 KB Output is correct
15 Correct 23 ms 8080 KB Output is correct
16 Correct 17 ms 7884 KB Output is correct
17 Correct 19 ms 7756 KB Output is correct
18 Correct 18 ms 7360 KB Output is correct
19 Correct 6 ms 6220 KB Output is correct
20 Correct 12 ms 6348 KB Output is correct
21 Correct 19 ms 8060 KB Output is correct
22 Correct 19 ms 8012 KB Output is correct
23 Correct 20 ms 8012 KB Output is correct
24 Correct 671 ms 48256 KB Output is correct
25 Correct 469 ms 13468 KB Output is correct
26 Correct 89 ms 12800 KB Output is correct
27 Correct 246 ms 13028 KB Output is correct
28 Correct 623 ms 59860 KB Output is correct
29 Correct 682 ms 58584 KB Output is correct
30 Correct 664 ms 57452 KB Output is correct
31 Correct 16 ms 6220 KB Output is correct
32 Correct 404 ms 13056 KB Output is correct
33 Correct 3 ms 5196 KB Output is correct
34 Correct 3 ms 5452 KB Output is correct
35 Correct 444 ms 39276 KB Output is correct
36 Correct 3 ms 5196 KB Output is correct
37 Correct 15 ms 7820 KB Output is correct
38 Correct 399 ms 51892 KB Output is correct
39 Correct 482 ms 65748 KB Output is correct