oj.uz

Submission #876225

# Submission time Handle Problem Language Result Execution time Memory
876225 2023-11-21T12:55:33 Z vjudge1 Tracks in the Snow (BOI13_tracks) C++17
91.25 / 100
 889 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<int, int> //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) (int)(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 int maxn = 5009;

int n,m;
string s[maxn];

bool vis[maxn][maxn];
int ans;

int x[] = {1,-1,0,0};
int y[] = {0,0,1,-1};
/////////////////////
//FUNCTIONS
void bfs(queue<pii> q1 , queue<pii> q2, int 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

/////////////////////
//MAIN
int main()
{
    FAST;
   	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;
}
/////////////////////
/*
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<int, int> >, std::queue<std::pair<int, int> >, 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 'int main()':
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:127:2: note: in expansion of macro 'For'
  127 |  For(i,n)cin >> s[i];
      |  ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4184 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 5 ms 3164 KB Output is correct
5 Correct 2 ms 2140 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 872 KB Output is correct
10 Correct 2 ms 1884 KB Output is correct
11 Correct 3 ms 1400 KB Output is correct
12 Correct 6 ms 2396 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 4064 KB Output is correct
16 Correct 10 ms 4188 KB Output is correct
17 Correct 7 ms 3676 KB Output is correct
18 Correct 5 ms 3164 KB Output is correct

Subtask #2
61.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23388 KB Output is correct
2 Correct 41 ms 13168 KB Output is correct
3 Correct 889 ms 912036 KB Output is correct
4 Correct 48 ms 20472 KB Output is correct
5 Runtime error 584 ms 1048576 KB Execution killed with signal 9
6 Correct 708 ms 79016 KB Output is correct
7 Correct 12 ms 23128 KB Output is correct
8 Correct 11 ms 23388 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 2 ms 4188 KB Output is correct
11 Correct 9 ms 19456 KB Output is correct
12 Correct 14 ms 17240 KB Output is correct
13 Correct 42 ms 13068 KB Output is correct
14 Correct 20 ms 8932 KB Output is correct
15 Correct 169 ms 214780 KB Output is correct
16 Correct 17 ms 6224 KB Output is correct
17 Correct 99 ms 30128 KB Output is correct
18 Correct 621 ms 820564 KB Output is correct
19 Correct 49 ms 20512 KB Output is correct
20 Correct 191 ms 191252 KB Output is correct
21 Correct 396 ms 515964 KB Output is correct
22 Runtime error 626 ms 1048576 KB Execution killed with signal 9
23 Correct 212 ms 49200 KB Output is correct
24 Runtime error 553 ms 1048576 KB Execution killed with signal 9
25 Runtime error 571 ms 1048576 KB Execution killed with signal 9
26 Correct 397 ms 43468 KB Output is correct
27 Correct 585 ms 56708 KB Output is correct
28 Correct 697 ms 79032 KB Output is correct
29 Correct 623 ms 77944 KB Output is correct
30 Correct 581 ms 72136 KB Output is correct
31 Correct 580 ms 81140 KB Output is correct
32 Correct 424 ms 55412 KB Output is correct