Submission #943277

#	Time	Username	Problem	Language	Result	Execution time	Memory
943277		yhkhoo	Portals (BOI14_portals)	C++17	0 / 100	13 ms	3732 KiB

portals

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

#define lb(vec, val) lower_bound((vec).begin(), (vec).end(), (val))
	
int main(){
	cin.tie(0); ios_base::sync_with_stdio(0);
	int r, c;
	cin >> r >> c;
	char m[r][c];
	vector<vector<int>> cw(c), rw(r);
	int S, C;
	for(int i=0; i<c; i++){
		cw[i].push_back(-1);
	}
	for(int i=0; i<r; i++){
		rw[i].push_back(-1);
		for(int j=0; j<c; j++){
			cin >> m[i][j];
			if(m[i][j] == '#'){
				rw[i].push_back(j);
				cw[j].push_back(i);
			}
			else if(m[i][j] == 'S'){
				S = i*c+j;
			}
			else if(m[i][j] == 'C'){
				C = i*c+j;
			}
		}
		rw[i].push_back(c);
	}
	for(int i=0; i<c; i++){
		cw[i].push_back(r);
	}
	vector<vector<pii>> al(r*c); //i*c+j
	for(int i=0; i<r; i++){
		for(int j=0; j<c; j++){
			int nn = i*c+j;
			if(m[i][j] == '#') continue;
			auto w3 = lb(cw[j],i);
			auto w1 = w3-1;
			auto w2 = lb(rw[i],j);
			auto w4 = w2-1;
			int dw = min(min(i-*w1, *w3-i), min(j-*w4, *w2-j));
			//if(i-*w1 > 2){
				al[nn].emplace_back((*w1+1)*c+j, dw);
			//}
			//if(*w3-i > 2){
				al[nn].emplace_back((*w3-1)*c+j, dw);
			//}
			//if(j-*w4 > 2){
				al[nn].emplace_back(i*c+(*w4+1), dw);
			//}
			//if(*w2-j > 2){
				al[nn].emplace_back(i*c+(*w2-1), dw);
			//}
		}
	}
	int dx[] = {1, -1, 0, 0};
	int dy[] = {0, 0, 1, -1};
	vector<bool> vi(r*c, 0);
	queue<int> q;
	vi[S] = 1;
	q.push(S);
	while(q.size()){
		int cn = q.front();
		q.pop();
		for(int k=0; k<4; k++){
			int cx = cn/c + dx[k];
			int cy = cn%c + dy[k];
			if(cx == -1 || cy == -1 || cx == r || cy == c) continue;
			if(m[cx][cy] == '#') continue;
			int knn = cx*c+cy;
			if(vi[knn]) continue;
			al[cn].emplace_back(knn, 1);
			al[knn].emplace_back(cn, 1);
			vi[knn] = true;
			q.push(knn);
		}
	}
	/*for(int i=0; i<r*c; i++){
		cout << i << ':';
		for(auto j: al[i]){
			cout << j.first << ' ' << j.second << ' ' << ' ';
		}
		cout << '\n';
	}*/
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	fill(vi.begin(), vi.end(), false);
	vector<int> dst(r*c, 1e9);
	dst[S] = 0;
	pq.emplace(0, S);
	while(pq.size()){
		auto[cd, cn] = pq.top();
		pq.pop();
		if(dst[cn] != cd) continue;
		if(vi[cn]) continue;
		for(auto [ccb, w] : al[cn]){
			if(dst[ccb] <= cd+w) continue;
			dst[ccb] = cd+w;
			pq.emplace(dst[ccb], ccb);
		}
		vi[cn] = true;
	}
	cout << dst[C];
	return 0;
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:108:15: warning: 'C' may be used uninitialized in this function [-Wmaybe-uninitialized]
  108 |  cout << dst[C];
      |               ^

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