Submission #466817

#	Time	Username	Problem	Language	Result	Execution time	Memory
466817		M4mou	Portals (BOI14_portals)	C++17	100 / 100	682 ms	65748 KiB

portals

#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 (stderr)

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 / 11
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30