Submission #624547

#	Time	Username	Problem	Language	Result	Execution time	Memory
624547		_Avocado_	Portals (BOI14_portals)	C++14	70 / 100	1095 ms	51656 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){
	if(i < n && i>=0 && j < m && j>=0 && graph[i][j] != '#' && dist[i][j] == -1) 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, -1));
	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)){
				dist[i+x][j+y] = dist[i][j] + 1;
				q.push({i+x, j+y});
			}
		}
	}
	
	return dist;
}

int dijkstra(auto&next, auto&w, auto&graph, pair<int, int>s, pair<int, int>e){
	vector<vector<int>>dist(n, vector<int>(m, -1));
	priority_queue<pair<pair<int, int>, int>>pq;
	pq.push({{0, s.first}, s.second});
	
	while(pq.size()){
		int d = pq.top().first.first;
		int i = pq.top().first.second;
		int j = pq.top().second;
		d = -d;
		pq.pop();
		
		if(dist[i][j] != -1) continue;
		
		dist[i][j] = d;
		
		for(auto [x, y]: delta){
			if(check(i+x, j+y, graph, dist)){
				pq.push({{-(d+1), i+x}, j+y});
			}
		}
		int cur = next[i][j];
		int nd = -(d+cur);
		if(check(w[i][j].up, j, graph, dist)) pq.push({{nd, w[i][j].up}, j});
		if(check(w[i][j].down, j, graph, dist)) pq.push({{nd, w[i][j].down}, j});
		if(check(i, w[i][j].right, graph, dist)) pq.push({{nd, i}, w[i][j].right});
		if(check(i, w[i][j].left, graph, dist)) pq.push({{nd, 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<<dijkstra(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){
      |                         ^~~~
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){
      |                                     ^~~~
portals.cpp:21:24: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   21 | vector<vector<int>>bfs(auto&graph, auto&start){
      |                        ^~~~
portals.cpp:21:36: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   21 | vector<vector<int>>bfs(auto&graph, auto&start){
      |                                    ^~~~
portals.cpp: In function 'std::vector<std::vector<int> > bfs(auto:3&, auto:4&)':
portals.cpp:24:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |  for(auto [x, y]: start){
      |           ^
portals.cpp:34:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |   for(auto [x, y]: delta){
      |            ^
portals.cpp: At global scope:
portals.cpp:45:14: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   45 | int dijkstra(auto&next, auto&w, auto&graph, pair<int, int>s, pair<int, int>e){
      |              ^~~~
portals.cpp:45:25: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   45 | int dijkstra(auto&next, auto&w, auto&graph, pair<int, int>s, pair<int, int>e){
      |                         ^~~~
portals.cpp:45:33: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   45 | int dijkstra(auto&next, auto&w, auto&graph, pair<int, int>s, pair<int, int>e){
      |                                 ^~~~
portals.cpp: In function 'int dijkstra(auto:5&, auto:6&, auto:7&, std::pair<int, int>, std::pair<int, int>)':
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: 0 / 30