oj.uz

Submission #573047

# Submission time Handle Problem Language Result Execution time Memory
573047 2022-06-05T16:54:01 Z fuad27 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 768 ms 386420 KB 
/*
 * Created: 2022-06-05 19:50
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
using namespace chrono;
// using namespace atcoder

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
const ll inf = 1e18;

#define pii		pair<int,int>
#define pll		pair<ll,ll>
#define vi		vector<int>
#define vll		vector<ll>
#define rep(i, a, b)	for(int i = (a);i<(b);i++)
#define repn(i, a, b)	for(int i = (a);i>=(b);i--)
#define ss		second
#define ff		first
#define mkp		make_pair
#define pb		push_back

#define all(x)		(x).begin(), (x).end()

template<typename T>
auto operator<<(ostream &os, T&v)->decltype(v.begin(), os){
	os << "[";
	int f = 0;
	for(auto i:v) {
		if(f++)os << ", ";
		os << i;
	}
	os << "]";
	return os;
}
template<typename F, typename S>
ostream& operator<<(ostream &os, pair<F, S> const &p) {
	return os << "(" << p.first << ", " << p.second << ")";
}
ostream& operator<<(ostream &os, string& s) {
	for(char i:s){
		os << i;
	}
	return os;
}
void debug(){}
template<typename T, typename... V>
void debug(T t, V... v) {
	cerr << t;
	if(sizeof...(v)) {
		cerr << ", "; debug(v...);
	}
}
#ifdef LOCAL
#define dbg(x...) cerr << "[" << #x << "]: " << "["; debug(x); cerr << "]\n";
#else
#define dbg(x...)
#endif
struct node {
	int x, y;
	int w;
	node() {
		w=0,x=0,y=0;
	}
};
int ax[] = {0, 0, 1, -1};
int ay[] = {1, -1, 0, 0};
void solve() {
	int n, m;cin >> n >> m;
	vector<string> v(n);
	rep(i,0,n)cin>>v[i];
	// ff -> 0, 1
	// ss -> x, y
	deque<node> dq;
	dq.push_back(node());
	vector<vector<bool>> vis(n, vector<bool> (m,0));
	ll ans = 1;
	while(!dq.empty()) {
		node at = dq.front();
		dq.pop_front();
		if(vis[at.x][at.y])continue;
		vis[at.x][at.y] = 1;
		ans = max(ans, (ll)at.w+1);
		for(int i = 0;i<4;i++) {
			if(at.x + ax[i] >= 0 && at.x + ax[i] < n && at.y + ay[i] >= 0 && at.y + ay[i] < m) {
				if(v[at.x+ax[i]][at.y+ay[i]]=='.')continue;
				if(v[at.x+ax[i]][at.y+ay[i]]==v[at.x][at.y]){
					node to = node();
					to.x=at.x + ax[i];
					to.y=at.y+ay[i];
					to.w = at.w;
					dq.push_front(to);
				}
				else {
					node to = node();
					to.x=at.x + ax[i];
					to.y=at.y+ay[i];
					to.w = at.w+1;
					dq.push_back(to);
				}
			}
		}
	}
	cout << ans << "\n";
}

int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	//~ cin >> t;
	while(t--) {
		solve();
	}
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1236 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 7 ms 1368 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 320 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 460 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 7 ms 724 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 456 KB Output is correct
15 Correct 11 ms 1048 KB Output is correct
16 Correct 14 ms 1240 KB Output is correct
17 Correct 8 ms 940 KB Output is correct
18 Correct 7 ms 1364 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 752 KB Output is correct
2 Correct 40 ms 2516 KB Output is correct
3 Correct 189 ms 20444 KB Output is correct
4 Correct 43 ms 5172 KB Output is correct
5 Correct 90 ms 11604 KB Output is correct
6 Correct 706 ms 71160 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 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 1 ms 360 KB Output is correct
13 Correct 38 ms 2512 KB Output is correct
14 Correct 23 ms 1748 KB Output is correct
15 Correct 10 ms 1764 KB Output is correct
16 Correct 20 ms 1364 KB Output is correct
17 Correct 95 ms 5640 KB Output is correct
18 Correct 41 ms 5464 KB Output is correct
19 Correct 55 ms 5060 KB Output is correct
20 Correct 49 ms 4736 KB Output is correct
21 Correct 112 ms 12004 KB Output is correct
22 Correct 91 ms 11608 KB Output is correct
23 Correct 198 ms 10316 KB Output is correct
24 Correct 90 ms 11704 KB Output is correct
25 Correct 217 ms 20416 KB Output is correct
26 Correct 768 ms 386420 KB Output is correct
27 Correct 631 ms 166924 KB Output is correct
28 Correct 718 ms 73136 KB Output is correct
29 Correct 731 ms 69792 KB Output is correct
30 Correct 761 ms 101004 KB Output is correct
31 Correct 579 ms 17668 KB Output is correct
32 Correct 612 ms 150084 KB Output is correct