oj.uz

Submission #883257

# Submission time Handle Problem Language Result Execution time Memory
883257 2023-12-05T00:43:23 Z xjonwang Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 524 ms 122760 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define ar array

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;

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

#define vt vector
#define pb push_back
#define pf push_front
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()
#define pll pair<ll, ll>
#define pii pair<int, int>
#define f first
#define s second

#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)

template<class T> bool umin(T& a, const T& b) {
	return b<a?a=b, 1:0;
}
template<class T> bool umax(T& a, const T& b) { 
	return a<b?a=b, 1:0;
} 

ll FIRSTTRUE(function<bool(ll)> f, ll lb, ll rb) {
	while(lb<rb) {
		ll mb=(lb+rb)/2;
		f(mb)?rb=mb:lb=mb+1; 
	} 
	return lb;
}
ll LASTTRUE(function<bool(ll)> f, ll lb, ll rb) {
	while(lb<rb) {
		ll mb=(lb+rb+1)/2;
		f(mb)?lb=mb:rb=mb-1; 
	} 
	return lb;
}

template<class A> void read(vt<A>& v);
template<class A, size_t S> void read(ar<A, S>& a);
template<class A, class B> void read(pair<A, B>& x);
template<class T> void read(T& x) {
	cin >> x;
}
void read(double& d) {
	string t;
	read(t);
	d=stod(t);
}
void read(long double& d) {
	string t;
	read(t);
	d=stold(t);
}
template<class H, class... T> void read(H& h, T&... t) {
	read(h);
	read(t...);
}
template<class A> void read(vt<A>& x) {
	EACH(a, x)
		read(a);
}
template<class A, size_t S> void read(array<A, S>& x) {
	EACH(a, x)
		read(a);
}
template<class A, class B> void read(pair<A, B>& x) {
	cin >> x.first >> x.second;
}


string to_string(char c) {
	return string(1, c);
}
string to_string(bool b) {
	return b?"true":"false";
}
string to_string(const char* s) {
	return string(s);
}
string to_string(string s) {
	return s;
}
string to_string(vt<bool> v) {
	string res;
	FOR(sz(v))
		res+=char('0'+v[i]);
	return res;
}

template<size_t S> string to_string(bitset<S> b) {
	string res;
	FOR(S)
		res+=char('0'+b[i]);
	return res;
}
template<class T> string to_string(T v) {
    bool f=1;
    string res;
    EACH(x, v) {
		if(!f)
			res+=' ';
		f=0;
		res+=to_string(x);
	}
    return res;
}
template<class A, class B> string to_string(pair<A, B>& x) {
	return to_string(x.first) + ' ' + to_string(x.second);
}

template<class A> void write(A x) {
	cout << to_string(x);
}
template<class H, class... T> void write(const H& h, const T&... t) { 
	write(h);
	write(t...);
}
void print() {
	write("\n");
}
template<class H, class... T> void print(const H& h, const T&... t) { 
	write(h);
	if(sizeof...(t))
		write(' ');
	print(t...);
}

int dr[4]={1, -1, 0, 0}, dc[4]={0, 0, 1, -1};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, ans=1; read(n, m);
	vt<vt<char>> v(n, vt<char>(m)); read(v);
	vt<vt<int>> vis(n, vt<int>(m, 0));
	vis[0][0]=1;
	deque<pii> q;
	q.pb({0, 0});
	while (sz(q)) {
		pii t=q.front(); q.pop_front();
		FOR(4) {
			int r=t.f+dr[i], c=t.s+dc[i];
			if (r>=0 && r<n && c>=0 && c<m && !vis[r][c] && v[r][c]!='.') {
				vis[r][c]=vis[t.f][t.s]+(v[r][c]!=v[t.f][t.s]);
				umax(ans, vis[r][c]);
				v[r][c]==v[t.f][t.s] ? q.pf({r, c}) : q.pb({r, c});
			}
		}
	}
	print(ans);
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1884 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1536 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 4 ms 860 KB Output is correct
13 Correct 3 ms 972 KB Output is correct
14 Correct 2 ms 976 KB Output is correct
15 Correct 9 ms 1880 KB Output is correct
16 Correct 10 ms 1884 KB Output is correct
17 Correct 7 ms 1708 KB Output is correct
18 Correct 5 ms 1372 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 38 ms 9556 KB Output is correct
3 Correct 279 ms 94672 KB Output is correct
4 Correct 67 ms 22452 KB Output is correct
5 Correct 180 ms 53496 KB Output is correct
6 Correct 516 ms 108164 KB Output is correct
7 Correct 2 ms 856 KB Output is correct
8 Correct 2 ms 856 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 1 ms 504 KB Output is correct
13 Correct 38 ms 9736 KB Output is correct
14 Correct 21 ms 5976 KB Output is correct
15 Correct 17 ms 6232 KB Output is correct
16 Correct 18 ms 4188 KB Output is correct
17 Correct 108 ms 24436 KB Output is correct
18 Correct 79 ms 23888 KB Output is correct
19 Correct 69 ms 22416 KB Output is correct
20 Correct 57 ms 20564 KB Output is correct
21 Correct 154 ms 55372 KB Output is correct
22 Correct 178 ms 53484 KB Output is correct
23 Correct 223 ms 45904 KB Output is correct
24 Correct 151 ms 53968 KB Output is correct
25 Correct 409 ms 94672 KB Output is correct
26 Correct 315 ms 122760 KB Output is correct
27 Correct 401 ms 121092 KB Output is correct
28 Correct 508 ms 108252 KB Output is correct
29 Correct 524 ms 106808 KB Output is correct
30 Correct 465 ms 110712 KB Output is correct
31 Correct 404 ms 61212 KB Output is correct
32 Correct 369 ms 109860 KB Output is correct