Submission #624587

#	Time	Username	Problem	Language	Result	Execution time	Memory
624587		_Avocado_	Portals (BOI14_portals)	C++14	100 / 100	255 ms	31172 KiB

portals

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

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

int n, m;
vector<pair<int, int>>delta = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

struct wall{
	int up, down, left, right;
};

int check(int i, int j, auto&graph, auto&dist, int op){
	if(i < n && i>=0 && j < m && j>=0 && graph[i][j] != '#'){
		if(op){
			if(dist[i][j] == 1e9) return 1;
			return 0;
		}
		return 1;
	}
	return 0;
}

vector<vector<int>>bfs(auto&graph, auto&start){
	queue<pair<int, int>>q;
	vector<vector<int>>dist(n, vector<int>(m, (int)1e9));
	for(auto [x, y]: start){
		q.push({x, y});
		dist[x][y] = 0;
	}
	
	while(q.size()){
		int i = q.front().first;
		int j = q.front().second;
		q.pop();
		
		for(auto [x, y]: delta){
			if(check(i+x, j+y, graph, dist, 1)){
				dist[i+x][j+y] = dist[i][j] + 1;
				q.push({i+x, j+y});
			}
		}
	}
	
	return dist;
}

int spfa(auto&next, auto&w, auto&graph, pair<int, int>s, pair<int, int>e){
	vector<vector<int>>dist(n, vector<int>(m, 1e9));
	queue<pair<int, int>>q;
	q.push({s.first, s.second});
	dist[s.first][s.second] = 0;
	
	while(q.size()){
		auto [i, j] = q.front();
		q.pop();
		
		for(auto [x, y]: delta){
			if(check(i+x, j+y, graph, dist, 0) && dist[i][j]+1 < dist[i+x][j+y]){
				dist[i+x][j+y] = dist[i][j]+1;
				q.push({i+x, j+y});
			}
		}
		
		int cur = next[i][j];
		int nd = dist[i][j]+cur;
		if(check(w[i][j].up, j, graph, dist, 0) && nd < dist[w[i][j].up][j]){
			dist[w[i][j].up][j] = nd;
			q.push({w[i][j].up, j});
		}
		if(check(w[i][j].down, j, graph, dist, 0) && nd < dist[w[i][j].down][j]){
			dist[w[i][j].down][j] = nd;
			q.push({w[i][j].down, j});
		}
		if(check(i, w[i][j].right, graph, dist, 0) && nd < dist[i][w[i][j].right]){
			dist[i][w[i][j].right] = nd;
			q.push({i, w[i][j].right});
		}
		if(check(i, w[i][j].left, graph, dist, 0) && nd < dist[i][w[i][j].left]){
			dist[i][w[i][j].left] = nd;
			q.push({i, w[i][j].left});
		}
	}
	
	return dist[e.first][e.second];
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//ifstream cin ("input.in");
	//ofstream cout ("output.out");
	
	cin>>n>>m;
	
	m += 2;
	
	vector<string>graph;
	string border;
	for(int i = 0; i<m; ++i) border += '#';
	graph.push_back(border);
	
	for(int i = 0; i<n; ++i){
		string s; cin>>s;
		graph.push_back("#");
		for(auto u: s) graph[i+1] += u;
		graph[i+1] += '#';
	}
	
	graph.push_back(border);
	/*
	for(auto u: graph){
		for(auto v: u) cout<<v;
		cout<<endl;
	}
	cout<<endl;
	*/
	
	n += 2;
	
	vector<vector<wall>>w(n, vector<wall>(m));
	
	pair<int, int>s, e;
	vector<pair<int, int>>start;
	
	for(int i = 0; i<n; ++i){
		int cur = 0;
		for(int j = 0; j<m; ++j){
			if(graph[i][j] == 'S') s = {i, j};
			if(graph[i][j] == 'C') e = {i, j};
			if(graph[i][j] == '#'){
				cur = j;
				start.push_back({i, j});
			}
			w[i][j].left = cur+1;
		}
		cur = m-1;
		for(int j = m-1; j>=0; --j){
			if(graph[i][j] == '#') cur = j;
			w[i][j].right = cur-1;
		}
	}
	
	for(int j = 0; j<m; ++j){
		int cur = 0;
		for(int i = 0; i<n; ++i){
			if(graph[i][j] == '#') cur = i;
			w[i][j].up = cur+1;
		}
		cur = n-1;
		for(int i = n-1; i>=0; --i){
			if(graph[i][j] == '#') cur = i;
			w[i][j].down = cur-1;
		}
	}
	
	vector<vector<int>>next = bfs(graph, start);
	
	/*
	for(auto u: next){
		for(auto v: u) cout<<v<<" ";
		cout<<endl;
	}
	cout<<endl;
	*/
	
	cout<<spfa(next, w, graph, s, e);
	
	
	cout<<'\n';
}

Compilation message (stderr)

portals.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
portals.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
portals.cpp:16:25: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   16 | int check(int i, int j, auto&graph, auto&dist, int op){
      |                         ^~~~
portals.cpp:16:37: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   16 | int check(int i, int j, auto&graph, auto&dist, int op){
      |                                     ^~~~
portals.cpp:27:24: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   27 | vector<vector<int>>bfs(auto&graph, auto&start){
      |                        ^~~~
portals.cpp:27:36: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   27 | vector<vector<int>>bfs(auto&graph, auto&start){
      |                                    ^~~~
portals.cpp: In function 'std::vector<std::vector<int> > bfs(auto:3&, auto:4&)':
portals.cpp:30:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |  for(auto [x, y]: start){
      |           ^
portals.cpp:40:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |   for(auto [x, y]: delta){
      |            ^
portals.cpp: At global scope:
portals.cpp:51:10: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   51 | int spfa(auto&next, auto&w, auto&graph, pair<int, int>s, pair<int, int>e){
      |          ^~~~
portals.cpp:51:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   51 | int spfa(auto&next, auto&w, auto&graph, pair<int, int>s, pair<int, int>e){
      |                     ^~~~
portals.cpp:51:29: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   51 | int spfa(auto&next, auto&w, auto&graph, pair<int, int>s, pair<int, int>e){
      |                             ^~~~
portals.cpp: In function 'int spfa(auto:5&, auto:6&, auto:7&, std::pair<int, int>, std::pair<int, int>)':
portals.cpp:58:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |   auto [i, j] = q.front();
      |        ^
portals.cpp:61:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |   for(auto [x, y]: delta){
      |            ^

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