oj.uz

Submission #876213

# Submission time Handle Problem Language Result Execution time Memory
876213 2023-11-21T12:46:44 Z vjudge1 Tracks in the Snow (BOI13_tracks) C++17
91.25 / 100
 803 ms 1048576 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define pb push_back //emplace_back
#define pp pop_back
#define pii pair<ll, ll> //pair<int, int>
#define all(x) (x).begin(),(x).end()
#define mp(a,b) make_pair(a , b)
#define lb lower_bound
#define ub upper_bound
#define sz(x) (ll)(x).size()
#define F first
#define S second
#define bg(x) (x).begin()
#define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
#define debug(x) cout << #x << " : " << x << endl
#define endl (char)(10)
#define arr(x) array<int , (x)>
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);
     
ll Sum(ll a , ll b , ll MOD)
{
    a %= MOD;
    b %= MOD;
    a += b;
    return a % MOD;
}
     
ll Mul(ll a , ll b , ll MOD)
{
    a %= MOD;
    b %= MOD;
    a *= b;
    return a % MOD;
}
     
ll Pow(ll a , ll b , ll MOD)
{
    ll res = 1;
    while(b)
    {
        if((b & 1))res = Mul(res , a , MOD);
        a = Mul(a , a , MOD);
        b >>= 1;
    }
    return res;
}
     
ll Min(ll a , ll b)
{
    if(a > b)return b;
    return a;
}
     
ll Max(ll a , ll b)
{
    if(a > b)return a;
    return b;
}
     
ll Ceil(ll a , ll b)
{
    if(a % b)return (a/b)+1;
    return a/b;
}
     
/////////////////////
//VALS
const ll maxn = 4009;

ll n,m;
string s[maxn];

bool vis[maxn][maxn];
ll ans;

ll x[4] = {1,-1,0,0};
ll y[4] = {0,0,1,-1};
/////////////////////
//FUNCTIONS
void bfs(queue<pii> q1 , queue<pii> q2, ll d)
{
	if(q1.empty())return;
	ans = d;
	while(!q1.empty())
	{
		pii p = q1.front();
		q1.pop();
		
		//debug(p.F);
		//debug(p.S);

		For(i,4)
		{
			if(p.F + x[i] < 0 or p.F + x[i] >= n or p.S + y[i] < 0 or p.S + y[i] >= m or s[p.F + x[i]][p.S + y[i]] == '.' or vis[p.F + x[i]][p.S + y[i]] == 1)continue;
			
			vis[p.F + x[i]][p.S + y[i]] = 1;

			bool flag = (s[p.F + x[i]][p.S + y[i]] == s[p.F][p.S]);

			//debug(i);
			//debug(flag);

			if(flag)
				q1.push(mp(p.F + x[i], p.S + y[i]));
			else
				q2.push(mp(p.F + x[i], p.S + y[i]));
		}
	}
	bfs(q2, q1, d+1);
}
/////////////////////
//SOLVE
void solve()
{
	cin >> n >> m;
	For(i,n)cin >> s[i];

	vis[0][0] = 1;

	queue<pii> q1, q2;
	q1.push(mp(0,0));
	bfs(q1,q2,1);

	cout << ans << endl;
	
	
}
/////////////////////
//MAIN
int main()
{
    FAST;
    ll t = 1;
//    cin >> t;
    while(t--)
    {
    solve();
    }
}
/////////////////////
/*
ZZZZZZZ     A        M     M     IIIIIII  N     N
     Z     A A      M M   M M       I     NN    N
    Z     A   A    M   M M   M      I     N N   N
   Z     AAAAAAA  M     M     M     I     N  N  N
  Z      A     A  M           M     I     N   N N
 Z       A     A  M           M     I     N    NN
ZZZZZZZ  A     A  M           M  IIIIIII  N     N  TREE
*/

Compilation message

tracks.cpp: In function 'void bfs(std::queue<std::pair<long long int, long long int> >, std::queue<std::pair<long long int, long long int> >, long long int)':
tracks.cpp:19:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   19 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
tracks.cpp:99:3: note: in expansion of macro 'For'
   99 |   For(i,4)
      |   ^~~
tracks.cpp: In function 'void solve()':
tracks.cpp:19:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   19 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
tracks.cpp:123:2: note: in expansion of macro 'For'
  123 |  For(i,n)cin >> s[i];
      |  ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4952 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 5 ms 3672 KB Output is correct
5 Correct 2 ms 2136 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 1884 KB Output is correct
11 Correct 2 ms 1372 KB Output is correct
12 Correct 4 ms 2648 KB Output is correct
13 Correct 2 ms 2140 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 9 ms 4552 KB Output is correct
16 Correct 10 ms 4956 KB Output is correct
17 Correct 7 ms 3932 KB Output is correct
18 Correct 6 ms 3424 KB Output is correct

Subtask #2
61.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 22872 KB Output is correct
2 Correct 35 ms 15160 KB Output is correct
3 Correct 803 ms 907916 KB Output is correct
4 Correct 62 ms 21332 KB Output is correct
5 Runtime error 498 ms 1048576 KB Execution killed with signal 9
6 Correct 671 ms 100860 KB Output is correct
7 Correct 11 ms 22616 KB Output is correct
8 Correct 11 ms 22876 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 2 ms 4192 KB Output is correct
11 Correct 8 ms 19036 KB Output is correct
12 Correct 9 ms 17156 KB Output is correct
13 Correct 39 ms 14948 KB Output is correct
14 Correct 20 ms 9816 KB Output is correct
15 Correct 153 ms 213636 KB Output is correct
16 Correct 20 ms 7256 KB Output is correct
17 Correct 100 ms 35172 KB Output is correct
18 Correct 593 ms 818672 KB Output is correct
19 Correct 45 ms 21072 KB Output is correct
20 Correct 155 ms 189584 KB Output is correct
21 Correct 386 ms 513064 KB Output is correct
22 Runtime error 475 ms 1048576 KB Execution killed with signal 9
23 Correct 212 ms 60756 KB Output is correct
24 Runtime error 487 ms 1048576 KB Execution killed with signal 9
25 Runtime error 550 ms 1048576 KB Execution killed with signal 9
26 Correct 311 ms 39692 KB Output is correct
27 Correct 511 ms 56268 KB Output is correct
28 Correct 684 ms 100704 KB Output is correct
29 Correct 655 ms 98516 KB Output is correct
30 Correct 544 ms 88524 KB Output is correct
31 Correct 573 ms 121432 KB Output is correct
32 Correct 419 ms 53512 KB Output is correct