oj.uz

Submission #606709

# Submission time Handle Problem Language Result Execution time Memory
606709 2022-07-26T07:53:00 Z baoq06 Patkice II (COCI21_patkice2) C++14
30 / 110
 2000 ms 45436 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

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

#define ll long long
#define all(x) x.begin(), x.end()
typedef pair<int, int> II;

template<typename T> bool maximize(T& a, T b) {return (a < b ? a = b, 1 : 0);}
template<typename T> bool minimize(T& a, T b) {return (a > b ? a = b, 1 : 0);}

const int N = 2e3 + 1;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

int n, m;
int xs, ys, xe, ye, d[N][N];
char a[N][N];

bool checkDir(const int &num, const char &dir)
{
	if(dir == '.') return 1;
	if(num == 0 && dir == '^') return 0;
	if(num == 1 && dir == '>') return 0;
	if(num == 2 && dir == 'v') return 0;
	if(num == 3 && dir == '<') return 0;
	return 1;
}

II trace[N][N];

void BFS()
{
	queue<II> Q;
	Q.push({xs, ys});
	d[xs][ys] = 0;
	
	while(Q.size())
	{
		auto cur = Q.front();
		Q.pop();
		
		for(int i = 0; i < 4; i++)
		{
			const int &X = cur.first + dx[i];
			const int &Y = cur.second + dy[i];
			
			if(X < 1 || X > n || Y < 1 || Y > m) continue;
			
			if(minimize(d[X][Y], d[cur.first][cur.second] + checkDir(i, a[cur.first][cur.second]))) 
			{
				trace[X][Y] = {cur.first, cur.second};
				Q.push({X, Y});
			}	
		}
	}
}

void Trace()
{
	II cur = {xe, ye};
	
	while(cur.first != xs || cur.second != ys)
	{
		II new_cur = trace[cur.first][cur.second];
		
		const int &X = new_cur.first;
		const int &Y = new_cur.second; 
		
		if(cur.first > X) a[X][Y] = 'v';
		else if(cur.first < X) a[X][Y] = '^';
		else if(cur.second < Y) a[X][Y] = '<';
		else a[X][Y] = '>';
		
		cur = new_cur;
	}
}

signed main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

	memset(d, 0x3f, sizeof(d));

    cin >> n >> m;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            if(a[i][j] == 'o') xs = i, ys = j;
            else if (a[i][j] == 'x') xe = i, ye = j;
        }
      
    BFS();
    Trace();
	
	cout << d[xe][ye] - 1 << '\n';
	
	a[xs][ys] = 'o';
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++) cout << a[i][j];
		cout << '\n';
	}

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15996 KB Output is correct
3 Correct 9 ms 15996 KB Output is correct
4 Correct 6 ms 16000 KB Output is correct
5 Correct 6 ms 15992 KB Output is correct

Subtask #2
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15996 KB Output is correct
3 Correct 9 ms 15996 KB Output is correct
4 Correct 6 ms 16000 KB Output is correct
5 Correct 6 ms 15992 KB Output is correct
6 Correct 494 ms 24632 KB Output is correct
7 Correct 268 ms 26492 KB Output is correct
8 Correct 1991 ms 35416 KB Output is correct
9 Correct 1188 ms 45436 KB Output is correct
10 Execution timed out 2059 ms 41812 KB Time limit exceeded
11 Halted 0 ms 0 KB -