Submission #1225296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225296		Amaarsaa	Portals (BOI14_portals)	C++20	20 / 100	19 ms	28740 KiB

portals

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pll = pair < ll, ll > ;
using plll =  pair < ll, pair < ll, ll > > ;
const ll N = 1e6 + 2;
ll a[1002][1002] = {0};
ll D[N] = {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 ++)  D[i] = 1e9;
	
	priority_queue < pll, vector < pll > , greater < pll > > pq;
	
	D[st] = 0;
	pq.push(make_pair(0, 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;
		cost = pq.top().first;
		pq.pop();
		if ( D[x] != cost) continue;
//		cout << x << " " << lft << " " << cost << endl;
		X = baruun[x];
		if ( D[X] > D[x] + 1 && B[X] == 0) {
			D[X] = D[x] + 1;
			pq.push(make_pair(D[X], X));
		} 
		X = zuun[x];
		if ( D[X] > D[x] + 1 && B[X] == 0) {
			D[X] = D[x] + 1;
			pq.push(make_pair(D[X], X));
		} 
		X = deesh[x];
		if ( D[X] > D[x] + 1 && B[X] == 0) {
			D[X] = D[x] + 1;
			pq.push(make_pair(D[X],X));
		} 
		X = doosh[x];
		if ( D[X] > D[x] + 1 && B[X] == 0) {
			D[X] = D[x] + 1;
			pq.push(make_pair(D[X], X));
		} 
		
		for ( ll X : nxt[x]) {
			if ( D[X] > D[x] + 1 && B[X] == 0) {
				D[X] = D[x] + 1;
				pq.push(make_pair(D[X], X));
			} 
		}
	} 
	cout << D[fn] << endl;
}

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