oj.uz

Submission #738775

# Submission time Handle Problem Language Result Execution time Memory
738775 2023-05-09T13:35:40 Z airths Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 743 ms 115460 KB 
/*
 * 
 * 	^v^
 * 
 */
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <iomanip>
#include <map>
#include <numeric>
#include <functional>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
#include <climits>
#include <cstdlib>
#include <chrono>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
// #define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define iamtefu ios_base::sync_with_stdio(false); cin.tie(0);
#define ll int
#define ld long double
#define sc(a) scanf("%lld", &a);
#define scv(a, n) vector<ll> a(n);fl(i,0,n){sc(a[i])}
#define prl(a) fl(i,0,a.size()){printf("%lld ", a[i]);}printf("\n");
#define fl(i,a,n) for (ll i(a); i<n; i++)
#define rfl(i,a,n) for (ll i(n-1); i>=a; i--)
#define print(a) for (auto x:a){cout<<x<<" ";} cout<<"\n";
#define tt int tt; cin>>tt; for(;tt--;)
ll gcd(ll a, ll b){
	if (b==0){
		return a;
	}
	return gcd(b, a%b);
}
ll pw(ll a, ll b, ll m){
	ll res=1;
	a%=m;
	while (b){
		if (b&1){
			res=(res*a)%m;
		}
		a=(a*a)%m;
		b/=2;
	}
	return res;
}
void scn(){
	ll n, m; cin>>n>>m;
	vector <string> a(n+1);
	fl(i,0,n){
		cin>>a[i];
	}
	vector <ll> di={1, 1, 0, -1, -1, -1, 0, 1};
	vector <ll> dj={0, 1, 1, 1, 0, -1, -1, -1};
	vector <vector <ll>> dis(n, vector <ll>(m, 0));
	dis[0][0] = 1;
	ll ans = 0;
	deque <pair<ll,ll>> q;
	q.push_back({0, 0});
	while (!q.empty()){
		auto j = q.front();
		q.pop_front();
		ans = max(ans, dis[j.first][j.second]);
		// cerr<<j.first<<" "<<j.second<<'\n';
		for (int d = 0; d<8; d+=2){
			ll i1 = j.first+di[d], j1 = j.second+dj[d];
			if (i1<0 || i1>=n || j1<0 || j1>=m || a[i1][j1]=='.' || dis[i1][j1]){
				continue;
			} else {
				dis[i1][j1] = dis[j.first][j.second]+(a[j.first][j.second]!=a[i1][j1]);
				if (a[j.first][j.second]==a[i1][j1]){
					q.push_front({i1, j1});
				} else {
					q.push_back({i1, j1});					
				}
			}
		}
	}
	cout<<ans<<'\n';
	// not necessarily distinct
}
int main(){
	iamtefu;
#if defined(airths)
	auto t1=chrono::high_resolution_clock::now();
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
	//
#endif
	// tt
	{
		scn();
	}
#if defined(airths)
	auto t2=chrono::high_resolution_clock::now();
	ld ti=chrono::duration_cast<chrono::nanoseconds>(t2-t1).count();
	ti*=1e-6;
	cerr<<"Time: "<<setprecision(12)<<ti;
	cerr<<"ms\n";
#endif
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1492 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 5 ms 1236 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 664 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 6 ms 808 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 12 ms 1620 KB Output is correct
16 Correct 11 ms 1492 KB Output is correct
17 Correct 9 ms 1492 KB Output is correct
18 Correct 5 ms 1236 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 35 ms 8088 KB Output is correct
3 Correct 231 ms 80888 KB Output is correct
4 Correct 63 ms 19064 KB Output is correct
5 Correct 134 ms 45476 KB Output is correct
6 Correct 743 ms 94968 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 1 ms 388 KB Output is correct
13 Correct 42 ms 8148 KB Output is correct
14 Correct 20 ms 4880 KB Output is correct
15 Correct 14 ms 5332 KB Output is correct
16 Correct 17 ms 3560 KB Output is correct
17 Correct 85 ms 20564 KB Output is correct
18 Correct 66 ms 20328 KB Output is correct
19 Correct 61 ms 19068 KB Output is correct
20 Correct 48 ms 17452 KB Output is correct
21 Correct 122 ms 47040 KB Output is correct
22 Correct 156 ms 45472 KB Output is correct
23 Correct 187 ms 39184 KB Output is correct
24 Correct 142 ms 45860 KB Output is correct
25 Correct 345 ms 80896 KB Output is correct
26 Correct 377 ms 111980 KB Output is correct
27 Correct 506 ms 115460 KB Output is correct
28 Correct 617 ms 94876 KB Output is correct
29 Correct 592 ms 92460 KB Output is correct
30 Correct 584 ms 98400 KB Output is correct
31 Correct 508 ms 52124 KB Output is correct
32 Correct 402 ms 105092 KB Output is correct