oj.uz

Submission #876240

# Submission time Handle Problem Language Result Execution time Memory
876240 2023-11-21T13:10:08 Z vjudge1 Tracks in the Snow (BOI13_tracks) C++14
91.25 / 100
 795 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 = 5000;

int n,m;
string s[maxn];

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

int x[] = {1,-1,0,0};
int y[] = {0,0,1,-1};
/////////////////////
//FUNCTIONS
inline 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]] == true)continue;
			
			vis[p.F + x[i]][p.S + y[i]] = true;

			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({0,0});

	bfs(q1,q2,1);

	cout << ans << '\n';
}
/////////////////////
/*
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 3308 KB Output is correct
5 Correct 2 ms 2136 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 1112 KB Output is correct
10 Correct 2 ms 1884 KB Output is correct
11 Correct 2 ms 1448 KB Output is correct
12 Correct 4 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 4208 KB Output is correct
16 Correct 12 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 10 ms 23388 KB Output is correct
2 Correct 34 ms 13068 KB Output is correct
3 Correct 795 ms 912468 KB Output is correct
4 Correct 45 ms 20512 KB Output is correct
5 Runtime error 494 ms 1048576 KB Execution killed with signal 9
6 Correct 709 ms 79360 KB Output is correct
7 Correct 11 ms 23132 KB Output is correct
8 Correct 11 ms 23376 KB Output is correct
9 Correct 2 ms 1152 KB Output is correct
10 Correct 2 ms 4188 KB Output is correct
11 Correct 9 ms 19292 KB Output is correct
12 Correct 9 ms 17220 KB Output is correct
13 Correct 35 ms 13152 KB Output is correct
14 Correct 20 ms 9052 KB Output is correct
15 Correct 164 ms 214760 KB Output is correct
16 Correct 20 ms 6228 KB Output is correct
17 Correct 100 ms 30196 KB Output is correct
18 Correct 600 ms 820540 KB Output is correct
19 Correct 51 ms 20564 KB Output is correct
20 Correct 159 ms 191164 KB Output is correct
21 Correct 394 ms 515752 KB Output is correct
22 Runtime error 469 ms 1048576 KB Execution killed with signal 9
23 Correct 211 ms 49256 KB Output is correct
24 Runtime error 484 ms 1048576 KB Execution killed with signal 9
25 Runtime error 530 ms 1048576 KB Execution killed with signal 9
26 Correct 381 ms 40108 KB Output is correct
27 Correct 509 ms 53288 KB Output is correct
28 Correct 685 ms 75708 KB Output is correct
29 Correct 643 ms 75072 KB Output is correct
30 Correct 547 ms 68812 KB Output is correct
31 Correct 568 ms 79280 KB Output is correct
32 Correct 430 ms 52180 KB Output is correct