Submission #1196259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196259		nuutsnoynton	Portals (BOI14_portals)	C++20	0 / 100	17 ms	23892 KiB

portals

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using plll =  pair < ll, pair < ll, ll > > ;
const ll N = 1e6 + 2;
ll a[1002][1002] = {0};
ll D[N][2] = {0};
ll B[N];
ll baruun[N], zuun[N], deesh[N], doosh[N];
vector < ll > nxt[N];
ll m, n;
ll Co(ll x, ll y) {
	return (x - 1) * m + y;
}
int main() {
	ll r, x, y, lft, I,X, cost, J, i, j, ans, t, st, fn;

	cin >> n >> m;
	
	for (i = 1; i <= n; i ++) {
		string str;
		
		cin >> str;
		
		for (j = 0; j < m; j ++) {
			if ( str[j] == '#') a[i][j + 1] = 1;
			if ( str[j] == 'S') {
				st = Co(i, j + 1);
			}
			if ( str[j] == 'C') {
				fn = Co(i, j + 1);
			}
			B[Co(i, j + 1)] = a[i][j + 1];
		}
	}
	
	for (i = 1; i <= n; i ++) {
		J = 0;
		for (j = 1; j <= m; j ++) {
			zuun[Co(i, j)] = Co(i, J + 1);
			if ( a[i][j] == 1) J = j;
			if ( j > 1 && a[i][j - 1] == 0) nxt[Co(i, j)].push_back(Co(i, j - 1));
		}
	}	
	for (i = 1; i <= n; i ++) {
		J = m + 1;
		for (j = m; j >= 1; j --) {
			baruun[Co(i, j)] = Co(i, J - 1);
			if ( a[i][j] == 1) J = j;
			if ( j < m && a[i][j + 1] == 0) nxt[Co(i, j)].push_back(Co(i, j + 1));
		}
	}
	for (j = 1; j <= m; j ++) {
		I = 0;
		for (i = 1; i <= n; i ++) {
			deesh[Co(i, j)] = Co(I + 1, j);
			if ( a[i][j] == 1) I = i;
			if ( i > 1 && a[i - 1][j] == 0) nxt[Co(i, j)].push_back(Co(i - 1, j));
		}
	}	
	for (j = 1; j <= m; j ++) {
		I = n + 1;
		for (i = n; i >= 1; i --) {
			doosh[Co(i, j)] = Co(I - 1, j);
			if ( a[i][j] == 1) I = i;
			if ( i < n && a[i + 1][j] == 0) nxt[Co(i, j)].push_back(Co(i + 1, j));
		}
	}
	
	for (i = 1; i <= n * m; i ++)  for (j = 0; j <= 1; j ++) D[i][j] = 1e9;
	
	priority_queue < plll, vector < plll > , greater < plll > > pq;
	
	D[st][1] = 0;
	pq.push(make_pair(0, make_pair(1, st)));
	for (i = 1; i <= n; i ++) {
		for (j = 1; j <= m; j ++) {
			r = Co(i, j);
//			cout<< deesh[r] << " " << doosh[r] << " " << baruun[r] << " " << zuun[r] << endl;
		}
	}
	while (!pq.empty()) {
		x = pq.top().second.second;
		lft = pq.top().second.first;
		cost = pq.top().first;
		pq.pop();
		if ( D[x][lft] != cost) continue;
//		cout << x << " " << lft << " " << cost << endl;
		if ( lft > 0) {
			X = baruun[x];
			if ( D[X][lft - 1] > D[x][lft] + 1 && B[X] == 0) {
				D[X][lft - 1] = D[x][lft] + 1;
				pq.push(make_pair(D[X][lft - 1], make_pair(lft - 1, X)));
			} 
			X = zuun[x];
			if ( D[X][lft - 1] > D[x][lft] + 1 && B[X] == 0) {
				D[X][lft - 1] = D[x][lft] + 1;
				pq.push(make_pair(D[X][lft - 1], make_pair(lft - 1, X)));
			} 
			X = deesh[x];
			if ( D[X][lft - 1] > D[x][lft] + 1 && B[X] == 0) {
				D[X][lft - 1] = D[x][lft] + 1;
				pq.push(make_pair(D[X][lft - 1], make_pair(lft - 1, X)));
			} 
			X = doosh[x];
			if ( D[X][lft - 1] > D[x][lft] + 1 && B[X] == 0) {
				D[X][lft - 1] = D[x][lft] + 1;
				pq.push(make_pair(D[X][lft - 1], make_pair(lft - 1, X)));
			} 
		}
		for ( ll X : nxt[x]) {
			if ( D[X][lft] > D[x][lft] + 1 && B[X] == 0) {
				D[X][lft] = D[x][lft] + 1;
				pq.push(make_pair(D[X][lft], make_pair(lft,  X)));
			} 
		}
	} 
	ans = min({D[fn][0], D[fn][1] });
	cout << ans << endl;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30