Submission #860404

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
860404	2023-10-12T19:31:39 Z	serifefedartar	Patkice II (COCI21_patkice2)	C++17	15 / 110	710 ms	524288 KB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 18; 
const ll MAXN = 1e5 + 100;

vector<pair<int,pair<int,int>>> graph[2005][2005], rev[2005][2005];
int dist[2005][2005], vis[2005][2005];
vector<string> grid;
pair<int,int> s, e;
void change(int row, int col, int nrow, int ncol) {
    if (row < 0 || col < 0 || grid[0].size() <= row || grid[0].size() <= col)    
        return ; 
    
	if (nrow > row)
		grid[row][col] = 'v';
	else if (nrow < row)
		grid[row][col] = '^';
	else if (ncol < col)
		grid[row][col] = '<';
	else
		grid[row][col] = '>'; 
}

void dfs(int row, int col, int target) {
	vis[row][col] = true;
	for (auto u : rev[row][col]) {
		int w = u.f;
		int nrow = u.s.f;
		int ncol = u.s.s;
		if (vis[nrow][ncol])
			continue;
		if (dist[nrow][ncol] + w == target) {
			change(nrow, ncol, row, col);
			dfs(nrow, ncol, target - w);
			return ;
		}
	}
}

int r, c;
bool check(int row, int col) {
	if (row >= 0 && col >= 0 && r > row && c > col)
		return true;
	return false; 
}

int main() {
	fast
	cin >> r >> c;

	for (int i = 0; i < 2005; i++) {
		for (int j = 0; j < 2005; j++)
			dist[i][j] = 1e8;
	}

	grid = vector<string>(r);
	for (int i = 0; i < r; i++)
		cin >> grid[i]; 

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (grid[i][j] == '>') {
			    if (check(i, j+1)) {
				    graph[i][j].push_back({0, {i, j+1}});
					rev[i][j+1].push_back({0, {i, j}});
				}
				if (check(i+1, j)) {
				    graph[i][j].push_back({1, {i+1, j}});
					rev[i+1][j].push_back({1, {i, j}});
				}
				if (check(i, j-1)) {
				    graph[i][j].push_back({1, {i, j-1}});
					rev[i][j-1].push_back({1, {i, j}});
				}
				if (check(i-1, j)) {
					graph[i][j].push_back({1, {i-1, j}});
					rev[i-1][j].push_back({1, {i, j}});
				}
			} else if (grid[i][j] == '<') {
				if (check(i, j+1)) {
					graph[i][j].push_back({1, {i, j+1}});
					rev[i][j+1].push_back({1, {i, j}});
				}
				if (check(i+1, j)) {
					graph[i][j].push_back({1, {i+1, j}});
					rev[i+1][j].push_back({1, {i, j}});
				}
				if (check(i, j-1)) {
					graph[i][j].push_back({0, {i, j-1}});
					rev[i][j-1].push_back({0, {i, j}});
				}
				if (check(i-1, j)) {
					graph[i][j].push_back({1, {i-1, j}});
					rev[i-1][j].push_back({1, {i, j}});
				}
			} else if (grid[i][j] == 'v') {
				if (check(i, j+1)) {
					graph[i][j].push_back({1, {i, j+1}});
					rev[i][j+1].push_back({1, {i, j}});
				}
				if (check(i+1, j)) {
					graph[i][j].push_back({0, {i+1, j}});
					rev[i+1][j].push_back({0, {i, j}});
				}
				if (check(i, j-1)) {
					graph[i][j].push_back({1, {i, j-1}});
					rev[i][j-1].push_back({1, {i, j}});
				}
				if (check(i-1, j)) {
					graph[i][j].push_back({1, {i-1, j}});
					rev[i-1][j].push_back({1, {i, j}});
				}
			} else if (grid[i][j] == '^') {
				if (check(i, j+1)) {
					graph[i][j].push_back({1, {i, j+1}});
					rev[i][j+1].push_back({1, {i, j}});
				}
				if (check(i+1, j)) {
					graph[i][j].push_back({1, {i+1, j}});
					rev[i+1][j].push_back({1, {i, j}});
				}
				if (check(i, j-1)) {
					graph[i][j].push_back({1, {i, j-1}});
					rev[i][j-1].push_back({1, {i, j}});
				}
				if (check(i-1, j)) {
					graph[i][j].push_back({0, {i-1, j}});
					rev[i-1][j].push_back({0, {i, j}});
				}
			} else if (grid[i][j] == '.') {
				if (check(i, j+1)) {
					graph[i][j].push_back({1, {i, j+1}});
					rev[i][j+1].push_back({1, {i, j}});
				}
				if (check(i+1, j)) {
					graph[i][j].push_back({1, {i+1, j}});
					rev[i+1][j].push_back({1, {i, j}});
				}
				if (check(i, j-1)) {
					graph[i][j].push_back({1, {i, j-1}});
					rev[i][j-1].push_back({1, {i, j}});
				}
				if (check(i-1, j)) {
					graph[i][j].push_back({1, {i-1, j}});
					rev[i-1][j].push_back({1, {i, j}});
				}
			} else if (grid[i][j] == 'o') {
				s = {i, j};
				if (check(i, j+1)) {
					graph[i][j].push_back({0, {i, j+1}});
					rev[i][j+1].push_back({0, {i, j}});
				}
				if (check(i+1, j)) {
					graph[i][j].push_back({0, {i+1, j}});
					rev[i+1][j].push_back({0, {i, j}});
				}
				if (check(i, j-1)) {
					graph[i][j].push_back({0, {i, j-1}});
					rev[i][j-1].push_back({0, {i, j}});
				}
				if (check(i-1, j)) {
					graph[i][j].push_back({0, {i-1, j}});
					rev[i-1][j].push_back({0, {i, j}});
				}
			} else
				e = {i, j};
		} 
	}

	deque<pair<int,int>> dq;
	dq.push_back(s);
	dist[s.f][s.s] = 0;
	while (!dq.empty()) {
		int row = dq.front().f;
		int col = dq.front().s;
		dq.pop_front();

		for (auto u : graph[row][col]) {
			int w = u.f;
			int nrow = u.s.f;
			int ncol = u.s.s;
			if (dist[nrow][ncol] > w + dist[row][col]) {
				dist[nrow][ncol] = w + dist[row][col];
				if (w == 1)
					dq.push_back({nrow, ncol});
				else
					dq.push_front({nrow, ncol});
			}
		}
	}

	cout << dist[e.f][e.s] << "\n";

	memset(vis, 0, sizeof(vis));
	dfs(e.f, e.s, dist[e.f][e.s]);
	grid[s.f][s.s] = 'o'; 
	for (int i = 0; i < r; i++) 
		cout << grid[i] << "\n";
}

Compilation message

Main.cpp: In function 'void change(int, int, int, int)':
Main.cpp:17:46: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   17 |     if (row < 0 || col < 0 || grid[0].size() <= row || grid[0].size() <= col)
      |                               ~~~~~~~~~~~~~~~^~~~~~
Main.cpp:17:71: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   17 |     if (row < 0 || col < 0 || grid[0].size() <= row || grid[0].size() <= col)
      |                                                        ~~~~~~~~~~~~~~~^~~~~~
Main.cpp:17:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   17 |     if (row < 0 || col < 0 || grid[0].size() <= row || grid[0].size() <= col)
      |     ^~
Main.cpp:20:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   20 |  if (nrow > row)
      |  ^~

Subtask #1

15.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	220496 KB	Output is correct
2	Partially correct	45 ms	220500 KB	Partially correct
3	Partially correct	44 ms	220756 KB	Partially correct
4	Correct	45 ms	220760 KB	Output is correct
5	Correct	46 ms	220500 KB	Output is correct

Subtask #2

0.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	220496 KB	Output is correct
2	Partially correct	45 ms	220500 KB	Partially correct
3	Partially correct	44 ms	220756 KB	Partially correct
4	Correct	45 ms	220760 KB	Output is correct
5	Correct	46 ms	220500 KB	Output is correct
6	Partially correct	184 ms	284496 KB	Partially correct
7	Correct	202 ms	287616 KB	Output is correct
8	Partially correct	462 ms	384592 KB	Partially correct
9	Correct	710 ms	494932 KB	Output is correct
10	Runtime error	529 ms	524288 KB	Execution killed with signal 9
11	Halted	0 ms	0 KB	-