oj.uz

Submission #1099643

# Submission time Handle Problem Language Result Execution time Memory
1099643 2024-10-11T22:35:58 Z stomic07 Portals (BOI14_portals) C++17
100 / 100
 239 ms 63160 KB 
#include <bits/stdc++.h>
//#include <windows.h>
using namespace std;
using mpt = array<pair<int, int>, 4>;

const int N = 1002;
int dozida[N][N];
int bio[N][N];
int ubacen[N][N];
mpt moguci[N][N];
int xmov[4] = {0, 1, 0, -1};
int ymov[4] = {-1, 0, 1, 0};

void reset(){
	for (int i=0; i<N; ++i){
		for (int j=0; j<N; ++j){
			dozida[i][j] = -1;
			bio[i][j] = -1;
			ubacen[i][j] = -1;
		}
	}
}

void set_mpt(const vector<string>& v){
	for (int row = 1; row < v.size() - 1; ++row){
		int wcol = 0;
		for (int col = 1; col < v[row].size() - 1; ++col){
			if (v[row][col] == '#'){
				wcol = col;
			}
			else{
				moguci[row][col][3] = make_pair(row, wcol + 1);
			}
		}
	}
	for (int row = 1; row < v.size() - 1; ++row){
		int wcol = v[row].size() - 1;
		for (int col = v[row].size() - 2; col > 0; --col){
			if (v[row][col] == '#'){
				wcol = col;
			}
			else{
				moguci[row][col][1] = make_pair(row, wcol - 1);
			}
		}
	}
	for (int col = 1; col < v[0].size() - 1; ++col){
		int wrow = 0;
		for (int row = 1; row < v.size() - 1; ++row){
			if (v[row][col] == '#'){
				wrow = row;
			}
			else{
				moguci[row][col][0] = make_pair(wrow + 1, col);
			}
		}
	}
	for (int col = 1; col < v[0].size() - 1; ++col){
		int wrow = v.size() - 1;
		for (int row = v.size() - 2; row > 0; --row){
			if (v[row][col] == '#'){
				wrow = row;
			}
			else{
				moguci[row][col][2] = make_pair(wrow - 1, col);
			}
		}
	}
}

void _set_mpt(const vector<string>& v){
	pair<int, int> lastpos;
	for (int i=1; i<v.size() - 1; ++i){
		for (int j=1; j<v[i].size() - 1; ++j){
			if (v[i][j] == '#') continue;
			if (v[i][j] == '.' && v[i][j-1] == '#'){
				lastpos.first = i;
				lastpos.second = j;
			}
			moguci[i][j][3] = lastpos;
		}
	}
	for (int i=1; i<v[0].size() - 1; ++i){
		for (int j=1; j<v.size() - 1; ++j){
			if (v[j][i] == '#') continue;
			if (v[j][i] == '.' && v[j-1][i] == '#'){
				lastpos.first = j;
				lastpos.second = i;
			}
			moguci[j][i][0] = lastpos;
		}
	}
	for (int i=1; i<v.size() - 1; ++i){
		for (int j=v[i].size() - 2; j>0; --j){
			if (v[i][j] == '#') continue;
			if (v[i][j] == '.' && v[i][j+1] == '#'){
				lastpos.first = i;
				lastpos.second = j;
			}
			moguci[i][j][1] = lastpos;
		}
	}
	for (int i=1; i<v[0].size() - 1; ++i){
		for (int j=v.size() - 2; j>0; --j){
			if (v[j][i] == '#') continue;
			if (v[j][i] == '.' && v[j+1][i] == '#'){
				lastpos.first = j;
				lastpos.second = i;
			}
			moguci[j][i][2] = lastpos;
		}
	}
}

void bfs_odzida(const vector<string>& v, vector<pair<int, int>>& fronta){
	vector<pair<int, int>> novi;
	for (int step = 0; !fronta.empty(); ++step){
		novi.clear();
		for (int i=0; i<fronta.size(); ++i){
			pair<int, int> curr = fronta[i];
			if (dozida[curr.first][curr.second] != -1) continue;
			dozida[curr.first][curr.second] = step;
			for (int j=0; j<4; ++j){
				int y = curr.first + ymov[j];
				int x = curr.second + xmov[j];
				if (v[y][x] == '#') continue;
				if (dozida[y][x] != -1) continue;
				novi.push_back(make_pair(y, x));
			}
		}
		fronta.swap(novi);
	}
}

mpt moguci_portal(const vector<string>& v, const pair<int, int>& point){
	return moguci[point.first][point.second];
//	mpt ret;
//	for (int i=0; i<4; ++i){
//		for (int j=1; ; ++j){
//			int y = point.first + ymov[i] * j;
//			int x = point.second + xmov[i] * j;
//			if (v[y][x] == '#'){
//				ret[i] = make_pair(y - ymov[i], x - xmov[i]);
//				break;
//			}
//		}
//	}
//	return ret;
}

void dijkstra(const vector<string>& v, const pair<int, int>& start, const pair<int, int>& cilj){
	using el_t = pair<int, pair<int, int>>;
	auto cmp = [](const auto& l, const auto& r){return r < l;};
	vector<el_t> que;
	que.push_back(make_pair(0, start));
	ubacen[start.first][start.second] = 0;
	while (!que.empty()){
		el_t poz = *que.begin();
		pop_heap(que.begin(), que.end(), cmp);
		que.pop_back();
		pair<int, int> curr = poz.second;
		if (bio[curr.first][curr.second] != -1) continue;
		bio[curr.first][curr.second] = poz.first;
		if (curr == cilj) return;
		for (int i=0; i<4; ++i){
			int y = curr.first + ymov[i];
			int x = curr.second + xmov[i];
			if (v[y][x] == '#') continue;
			if (ubacen[y][x] != -1 && ubacen[y][x] <= poz.first + 1) continue;
			que.push_back(make_pair(poz.first + 1, make_pair(y, x)));
			push_heap(que.begin(), que.end(), cmp);
			ubacen[y][x] = poz.first + 1;
		}
		auto krajevi = moguci_portal(v, curr);
		for (int i=0; i<4; ++i){
			int y = krajevi[i].first;
			int x = krajevi[i].second;
			int val = poz.first + dozida[curr.first][curr.second] + 1;
			if (ubacen[y][x] != -1 && ubacen[y][x] <= val) continue;
			que.push_back(make_pair(val, krajevi[i]));
			push_heap(que.begin(), que.end(), cmp);
			ubacen[y][x] = val;
		}
	}
}

int main(){
	reset();
//	auto t0 = GetTickCount();
//	ifstream in("gigant.txt");
	int n, m;
	cin >> n >> m;
	string nule = "";
	for (int i=0; i<m+2; ++i){
		nule += '#';
	}
	vector<string> v;
	v.push_back(nule);
	pair<int, int> start;
	pair<int, int> cilj;
	for (int i=0; i<n; ++i){
		string s;
		cin >> s;
		for (int j=0; j<s.size(); ++j){
			if (s[j] == 'S'){
				start.first = i+1;
				start.second = j+1;
			}
			if (s[j] == 'C'){
				cilj.first = i+1;
				cilj.second = j+1;
			}
		}
		s = "#" + s + "#";
		v.push_back(s);
	}
	v.push_back(nule);
	set_mpt(v);
	vector<pair<int, int>> zidni;
	for (int i=1; i<n+1; ++i){
		for (int j=1; j<m+1; ++j){
			if (v[i][j] == '#') continue;
			for (int k=0; k<4; ++k){
				if (v[i + ymov[k]][j + xmov[k]] == '#'){
					zidni.push_back(make_pair(i, j));
					break;
				}
			}
		}
	}
//	auto t1 = GetTickCount();
//	cout << t1 - t0 << "\n";
	bfs_odzida(v, zidni);
//	auto t2 = GetTickCount();
//	cout << t2 - t0 << "\n";
	dijkstra(v, start, cilj);
	cout << bio[cilj.first][cilj.second] << "\n";
//	auto t3 = GetTickCount();
//	cout << t3 - t0 << "\n";
	return 0;
}

Compilation message

portals.cpp: In function 'void set_mpt(const std::vector<std::__cxx11::basic_string<char> >&)':
portals.cpp:25:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for (int row = 1; row < v.size() - 1; ++row){
      |                    ~~~~^~~~~~~~~~~~~~
portals.cpp:27:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for (int col = 1; col < v[row].size() - 1; ++col){
      |                     ~~~~^~~~~~~~~~~~~~~~~~~
portals.cpp:36:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for (int row = 1; row < v.size() - 1; ++row){
      |                    ~~~~^~~~~~~~~~~~~~
portals.cpp:47:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for (int col = 1; col < v[0].size() - 1; ++col){
      |                    ~~~~^~~~~~~~~~~~~~~~~
portals.cpp:49:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (int row = 1; row < v.size() - 1; ++row){
      |                     ~~~~^~~~~~~~~~~~~~
portals.cpp:58:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for (int col = 1; col < v[0].size() - 1; ++col){
      |                    ~~~~^~~~~~~~~~~~~~~~~
portals.cpp: In function 'void _set_mpt(const std::vector<std::__cxx11::basic_string<char> >&)':
portals.cpp:73:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for (int i=1; i<v.size() - 1; ++i){
      |                ~^~~~~~~~~~~~~
portals.cpp:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for (int j=1; j<v[i].size() - 1; ++j){
      |                 ~^~~~~~~~~~~~~~~~
portals.cpp:83:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for (int i=1; i<v[0].size() - 1; ++i){
      |                ~^~~~~~~~~~~~~~~~
portals.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for (int j=1; j<v.size() - 1; ++j){
      |                 ~^~~~~~~~~~~~~
portals.cpp:93:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for (int i=1; i<v.size() - 1; ++i){
      |                ~^~~~~~~~~~~~~
portals.cpp:103:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |  for (int i=1; i<v[0].size() - 1; ++i){
      |                ~^~~~~~~~~~~~~~~~
portals.cpp: In function 'void bfs_odzida(const std::vector<std::__cxx11::basic_string<char> >&, std::vector<std::pair<int, int> >&)':
portals.cpp:119:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |   for (int i=0; i<fronta.size(); ++i){
      |                 ~^~~~~~~~~~~~~~
portals.cpp: In function 'int main()':
portals.cpp:204:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |   for (int j=0; j<s.size(); ++j){
      |                 ~^~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 4 ms 12124 KB Output is correct
4 Correct 4 ms 12124 KB Output is correct
5 Correct 4 ms 12120 KB Output is correct
6 Correct 4 ms 12124 KB Output is correct
7 Correct 3 ms 12056 KB Output is correct
8 Correct 4 ms 12124 KB Output is correct
9 Correct 4 ms 12216 KB Output is correct
10 Correct 3 ms 12124 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12124 KB Output is correct
2 Correct 4 ms 12124 KB Output is correct
3 Correct 4 ms 12124 KB Output is correct
4 Correct 4 ms 12012 KB Output is correct
5 Correct 4 ms 12124 KB Output is correct
6 Correct 4 ms 12256 KB Output is correct
7 Correct 4 ms 12124 KB Output is correct
8 Correct 3 ms 12232 KB Output is correct
9 Correct 4 ms 12380 KB Output is correct
10 Correct 4 ms 12380 KB Output is correct
11 Correct 4 ms 12380 KB Output is correct
12 Correct 5 ms 12376 KB Output is correct
13 Correct 4 ms 12380 KB Output is correct
14 Correct 4 ms 12124 KB Output is correct
15 Correct 5 ms 12380 KB Output is correct
16 Correct 4 ms 12124 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 4 ms 12124 KB Output is correct
3 Correct 4 ms 12124 KB Output is correct
4 Correct 4 ms 12124 KB Output is correct
5 Correct 9 ms 14784 KB Output is correct
6 Correct 10 ms 14804 KB Output is correct
7 Correct 9 ms 14884 KB Output is correct
8 Correct 7 ms 14808 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12120 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 4 ms 12124 KB Output is correct
4 Correct 4 ms 12124 KB Output is correct
5 Correct 4 ms 12056 KB Output is correct
6 Correct 4 ms 12124 KB Output is correct
7 Correct 4 ms 12124 KB Output is correct
8 Correct 4 ms 12216 KB Output is correct
9 Correct 5 ms 12376 KB Output is correct
10 Correct 7 ms 12380 KB Output is correct
11 Correct 4 ms 12556 KB Output is correct
12 Correct 4 ms 12380 KB Output is correct
13 Correct 4 ms 12380 KB Output is correct
14 Correct 9 ms 14804 KB Output is correct
15 Correct 9 ms 14808 KB Output is correct
16 Correct 9 ms 14840 KB Output is correct
17 Correct 9 ms 14808 KB Output is correct
18 Correct 10 ms 14940 KB Output is correct
19 Correct 6 ms 14172 KB Output is correct
20 Correct 8 ms 14340 KB Output is correct
21 Correct 9 ms 14704 KB Output is correct
22 Correct 9 ms 14808 KB Output is correct
23 Correct 10 ms 14808 KB Output is correct
24 Correct 11 ms 14208 KB Output is correct
25 Correct 3 ms 12124 KB Output is correct
26 Correct 4 ms 12376 KB Output is correct
27 Correct 4 ms 12120 KB Output is correct
28 Correct 7 ms 14804 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 4 ms 12124 KB Output is correct
3 Correct 4 ms 12124 KB Output is correct
4 Correct 4 ms 12156 KB Output is correct
5 Correct 4 ms 12124 KB Output is correct
6 Correct 4 ms 12124 KB Output is correct
7 Correct 4 ms 12124 KB Output is correct
8 Correct 4 ms 12124 KB Output is correct
9 Correct 3 ms 12472 KB Output is correct
10 Correct 4 ms 12376 KB Output is correct
11 Correct 4 ms 12380 KB Output is correct
12 Correct 4 ms 12516 KB Output is correct
13 Correct 5 ms 12504 KB Output is correct
14 Correct 9 ms 14756 KB Output is correct
15 Correct 10 ms 14808 KB Output is correct
16 Correct 9 ms 14812 KB Output is correct
17 Correct 10 ms 14812 KB Output is correct
18 Correct 11 ms 14940 KB Output is correct
19 Correct 6 ms 14376 KB Output is correct
20 Correct 9 ms 14176 KB Output is correct
21 Correct 10 ms 14808 KB Output is correct
22 Correct 9 ms 14808 KB Output is correct
23 Correct 10 ms 14808 KB Output is correct
24 Correct 180 ms 56644 KB Output is correct
25 Correct 239 ms 45128 KB Output is correct
26 Correct 69 ms 45648 KB Output is correct
27 Correct 136 ms 45808 KB Output is correct
28 Correct 143 ms 62344 KB Output is correct
29 Correct 152 ms 62392 KB Output is correct
30 Correct 148 ms 62388 KB Output is correct
31 Correct 9 ms 14168 KB Output is correct
32 Correct 193 ms 45652 KB Output is correct
33 Correct 3 ms 12124 KB Output is correct
34 Correct 4 ms 12484 KB Output is correct
35 Correct 118 ms 44748 KB Output is correct
36 Correct 3 ms 12124 KB Output is correct
37 Correct 6 ms 14892 KB Output is correct
38 Correct 99 ms 63160 KB Output is correct
39 Correct 87 ms 41916 KB Output is correct