Submission #943251

#	Time	Username	Problem	Language	Result	Execution time	Memory
943251		teacup	Portals (BOI14_portals)	C++14	0 / 100	1102 ms	34300 KiB

portals

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define vi vector<int>
#define iii tuple<int,int,int>
typedef vector<ii> vii;
int R,C,Sx,Sy,Cx,Cy;
char G[1005][1005];
vi AL[1005][1005];
vii AL2[300000];
ii Start[300000];
ii End[300000];

int32_t main(){
	cin>>R>>C;
	for (int i=0; i<R; i++){
		for (int j=0; j<C; j++){
			cin>>G[i][j];
			if (G[i][j]=='S'){
				Sx = i; Sy = j;
			}if (G[i][j]=='C'){
				Cx = i; Cy = j;
			}
		}
	}
	
	int cnt=0, num=0;
	for (int i=0; i<R; i++){
		for (int j=0; j<C; j++){
			if (G[i][j]=='#'){
				if (num>0) End[cnt]=ii({i,j-1});
				cnt++;
				num=0;
			}else{
				if (num==0) Start[cnt]=ii({i,j});
				AL2[cnt].emplace_back(i,j);
				AL[i][j].emplace_back(cnt);
				num++;
			}
		}
		if (num>0) End[cnt]=ii({i,C-1});
		cnt++;
		num=0;
	}
	Start[cnt] = make_pair(0,0);
	for (int j=0; j<C; j++){
		for (int i=0; i<R; i++){
			if (G[i][j]=='#'){
				if (num>0) End[cnt]=make_pair(i-1,j);
				cnt++;
				num=0;
			}else{
				if (num==0) Start[cnt]=make_pair(i,j);
				AL2[cnt].emplace_back(i,j);
				AL[i][j].emplace_back(cnt);
				num++;
			}
		}
		if (num>0) End[cnt]=make_pair(R-1,j);
		cnt++;
		num=0;
	}
	
	queue<ii> BFS;
	map<ii,ii> prev;
	prev[ii(Sx, Sy)] = make_pair(-1,-1);
	BFS.push(make_pair(Sx,Sy));
	while (!BFS.empty()){
		ii curr = BFS.front(); BFS.pop();
		ii adj;
		if (curr.second==-1){
			for (auto nb : AL[curr.first][curr.second]){
				pair<int,int> p_ = make_pair(nb, -1);
				if (prev.find(p_)==prev.end()){
					prev[p_]=curr;
					BFS.push(p_);
				}
			}
		}else{
			for (auto nb : AL2[curr.first]){
				if (prev.find(nb)==prev.end()){
					prev[nb]=curr;
					BFS.push(nb);
				}
			}
		}
	}
	
	ii curr = make_pair(Cx,Cy);
	int curr_extra;
	int ans=0;
	while (curr != ii({-1,-1})){
		ii parent = prev.find(curr)->second;
		if (parent.second == -1){
			curr_extra = parent.first;
			continue;
		}
		ii S_=Start[curr_extra], E_=End[curr_extra];
		if (curr.first == parent.first){
			// x is the same
			int top = min(curr.second, parent.second);
			int bot = max(curr.second, parent.second);
			ans += min(bot-top, E_.second - bot + top - S_.second + 1);
		}else if (curr.second == parent.second){
			// y is the same
			int top = min(curr.first, parent.first);
			int bot = max(curr.first, parent.first);
			ans += min(bot-top, E_.first - bot + top - S_.first + 1);
		}
		curr = parent;
	}
	cout<<ans;
}

Compilation message (stderr)

portals.cpp: In function 'int32_t main()':
portals.cpp:73:45: warning: array subscript -1 is below array bounds of 'std::vector<long long int> [1005]' [-Warray-bounds]
   73 |    for (auto nb : AL[curr.first][curr.second]){
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~^
portals.cpp:99:28: warning: 'curr_extra' may be used uninitialized in this function [-Wmaybe-uninitialized]
   99 |   ii S_=Start[curr_extra], E_=End[curr_extra];
      |                            ^~

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