Submission #396124

#	Time	Username	Problem	Language	Result	Execution time	Memory
396124		Nicholas_Patrick	Portals (BOI14_portals)	C++17	100 / 100	829 ms	183556 KiB

portals

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

char getTile(){
	for(char c;;){
		c=getchar();
		for(char s: ".#SC")
			if(s==c)
				return c;
	}
}
int main(){
	int r, c;
	scanf("%d%d", &r, &c);
	int v=r*c;
	vector<char> board(v);
	for(auto& i: board)
		i=getTile();
	vector<vector<int>> adjLis(v);
	vector<vector<int>> disLis(v);
	vector<int> walldist(v, r);
	int s, t;
	for(int i=0; i<r; i++)for(int j=0; j<c; j++){
		if(board[i*c+j]=='S'){
			s=i*c+j;
			board[i*c+j]='.';
		}else if(board[i*c+j]=='C'){
			t=i*c+j;
			board[i*c+j]='.';
		}
		walldist[i*c+j]=min({i+1, j+1, r-i, c-j});
		if(board[i*c+j]=='#'){
			walldist[i*c+j]=0;
			continue;
		}
		if(i and board[(i-1)*c+j]=='.'){
			adjLis[i*c+j].push_back((i-1)*c+j);
			disLis[i*c+j].push_back(1);
			adjLis[(i-1)*c+j].push_back(i*c+j);
			disLis[(i-1)*c+j].push_back(1);
		}
		if(j and board[i*c+j-1]=='.'){
			adjLis[i*c+j].push_back(i*c+j-1);
			disLis[i*c+j].push_back(1);
			adjLis[i*c+j-1].push_back(i*c+j);
			disLis[i*c+j-1].push_back(1);
		}
	}
	for(int i=0; i<r; i++){
		for(int j=1; j<c; j++)
			walldist[i*c+j]=min(walldist[i*c+j], walldist[i*c+j-1]+1);
		for(int j=c; --j;)
			walldist[i*c+j-1]=min(walldist[i*c+j-1], walldist[i*c+j]+1);
	}
	for(int j=0; j<c; j++){
		for(int i=1; i<r; i++)
			walldist[i*c+j]=min(walldist[i*c+j], walldist[(i-1)*c+j]+1);
		for(int i=r; --i;)
			walldist[(i-1)*c+j]=min(walldist[(i-1)*c+j], walldist[i*c+j]+1);
	}
	vector<int> destination(v);
	for(int i=0; i<r; i++)for(int j=c; j--;){
		if(i==0 or board[(i-1)*c+j]=='#'){
			destination[i*c+j]=i*c+j;
		}else{
			destination[i*c+j]=destination[(i-1)*c+j];
		}
		if(board[i*c+j]=='.'){
			adjLis[i*c+j].push_back(destination[i*c+j]);
			disLis[i*c+j].push_back(walldist[i*c+j]);
		}
	}
	for(int i=r; i--;)for(int j=c; j--;){
		if(i==r-1 or board[(i+1)*c+j]=='#'){
			destination[i*c+j]=i*c+j;
		}else{
			destination[i*c+j]=destination[(i+1)*c+j];
		}
		if(board[i*c+j]=='.'){
			adjLis[i*c+j].push_back(destination[i*c+j]);
			disLis[i*c+j].push_back(walldist[i*c+j]);
		}
	}
	for(int i=r; i--;)for(int j=0; j<c; j++){
		if(j==0 or board[i*c+j-1]=='#'){
			destination[i*c+j]=i*c+j;
		}else{
			destination[i*c+j]=destination[i*c+j-1];
		}
		if(board[i*c+j]=='.'){
			adjLis[i*c+j].push_back(destination[i*c+j]);
			disLis[i*c+j].push_back(walldist[i*c+j]);
		}
	}
	for(int i=r; i--;)for(int j=c; j--;){
		if(j==c-1 or board[i*c+j+1]=='#'){
			destination[i*c+j]=i*c+j;
		}else{
			destination[i*c+j]=destination[i*c+j+1];
		}
		if(board[i*c+j]=='.'){
			adjLis[i*c+j].push_back(destination[i*c+j]);
			disLis[i*c+j].push_back(walldist[i*c+j]);
		}
	}
	vector<vector<int>> dijkstra(v);
	vector<int> dist(v, v);
	dist[s]=0;
	dijkstra[0].push_back(s);
	for(int i=0; i<v; i++){
		for(int j: dijkstra[i]){
			if(dist[j]!=i)
				continue;
			if(j==t){
				printf("%d\n", i);
				return 0;
			}
			for(int k=adjLis[j].size(); k--;){
				if(dist[j]+disLis[j][k]<dist[adjLis[j][k]]){
					dist[adjLis[j][k]]=dist[j]+disLis[j][k];
					dijkstra[dist[adjLis[j][k]]].push_back(adjLis[j][k]);
				}
			}
		}
	}
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   16 |  scanf("%d%d", &r, &c);
      |  ~~~~~^~~~~~~~~~~~~~~~
portals.cpp:116:4: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
  116 |    if(j==t){
      |    ^~

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