oj.uz

Submission #876219

# Submission time Handle Problem Language Result Execution time Memory
876219 2023-11-21T12:50:00 Z vjudge1 Tracks in the Snow (BOI13_tracks) C++17
91.25 / 100
 707 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 = 5009;

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 11 ms 5208 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 6 ms 3676 KB Output is correct
5 Correct 3 ms 2416 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 1116 KB Output is correct
10 Correct 2 ms 2140 KB Output is correct
11 Correct 2 ms 1628 KB Output is correct
12 Correct 4 ms 2652 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 4956 KB Output is correct
16 Correct 11 ms 5212 KB Output is correct
17 Correct 7 ms 4188 KB Output is correct
18 Correct 6 ms 3676 KB Output is correct

Subtask #2
61.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23384 KB Output is correct
2 Correct 36 ms 15956 KB Output is correct
3 Correct 706 ms 912464 KB Output is correct
4 Correct 49 ms 23108 KB Output is correct
5 Runtime error 472 ms 1048576 KB Execution killed with signal 9
6 Correct 686 ms 104472 KB Output is correct
7 Correct 11 ms 23132 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 19340 KB Output is correct
12 Correct 9 ms 17240 KB Output is correct
13 Correct 37 ms 15980 KB Output is correct
14 Correct 21 ms 10612 KB Output is correct
15 Correct 154 ms 214872 KB Output is correct
16 Correct 18 ms 7708 KB Output is correct
17 Correct 105 ms 36952 KB Output is correct
18 Correct 595 ms 820564 KB Output is correct
19 Correct 47 ms 23120 KB Output is correct
20 Correct 150 ms 191312 KB Output is correct
21 Correct 389 ms 516148 KB Output is correct
22 Runtime error 484 ms 1048576 KB Execution killed with signal 9
23 Correct 219 ms 63060 KB Output is correct
24 Runtime error 512 ms 1048576 KB Execution killed with signal 9
25 Runtime error 527 ms 1048576 KB Execution killed with signal 9
26 Correct 407 ms 43152 KB Output is correct
27 Correct 496 ms 60180 KB Output is correct
28 Correct 707 ms 104476 KB Output is correct
29 Correct 645 ms 102600 KB Output is correct
30 Correct 593 ms 92272 KB Output is correct
31 Correct 599 ms 124664 KB Output is correct
32 Correct 479 ms 57532 KB Output is correct