Submission #416861

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
416861	2021-06-03T06:22:17 Z	Recedivies	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	900 ms	130888 KB

tracks

/*
 * Author : recedivies
 * Problem Link : https://tlx.toki.id/problems/osn-2017/2B/
 * Mei 20, 2021
 */
#include <bits/stdc++.h>
using namespace std; 

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef string str;

#define io() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define sz(a) ((int)(a).size())
#define mset(a, b) memset(a, b, sizeof(a))
#define print(a, n) for(int _i = 0 ; _i < n ; _i++) cout << a[_i] << " "; cout << '\n';
#define print2(a, n, m) for(int _i = 0 ; _i < n ; _i++){for(int _j = 0 ; _j < m ; _j++){cout << a[_i][_j] << " ";} cout << '\n';}

int dd[123];

ll Read() {
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    ch = getchar();
  }
  ll v = 0;
  while ('0' <= ch && ch <= '9') {
    v = v * 10 + (int) (ch - '0');
    ch = getchar();
  }
  return v;
}
 
void Write(ll x) {
  int len = 0;
  while (x > 0) {
    dd[len++] = x % 10;
    x /= 10;
  }
  for (int i = len - 1; i >= 0; i--) {
    putchar('0' + dd[i]);
  }
  if (len == 0) {
    putchar('0');
  }
  putchar(' ');
}

template < typename F, typename S >
ostream& operator << ( ostream& os, const pair< F, S > & p ) {
    return os << "(" << p.first << ", " << p.second << ")";
}
template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
    os << "{";
    for (auto it = v.begin(); it != v.end(); ++it)
    {
        if ( it != v.begin() )
            os << ", ";
        os << *it;
    }
    return os << "}";
}
template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
    os << "[";
    for (auto it = v.begin(); it != v.end(); ++it)
    {
        if ( it != v.begin())
            os << ", ";
        os << *it;
    }
    return os << "]";
}
template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v ) {
    os << "[";
    for (auto it = v.begin(); it != v.end(); ++it)
    {
        if ( it != v.begin() )
            os << ", ";
        os << it -> first << " = " << it -> second ;
    }
    return os << "]\n";
}
#define deb(args...) do {cerr << #args << " = "; faltu(args); } while(0)
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false); debug("%s Time : %.4fs", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))

void faltu () {
    cerr << endl;
}
template <typename T>
void faltu( T a[], int n ) {
    for (int i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}
template <typename T, typename ... hello>
void faltu( T arg, const hello &... rest) {
    cerr << arg << ' ';
    faltu(rest...);
}
 
template <class T> T egcd(T a , T b , T &x , T &y){T gcd , xt , yt;if(a == 0){gcd = b;x = 0 , y = 1;}else {gcd = egcd(b % a , a , xt , yt);x = yt - (b/a)*xt; y = xt;}return gcd;}
template <class T> T expo(T base , T exp , T mod){T res = 1;base = base % mod;while (exp > 0){if (exp & 1)res = (res*base) % mod;exp = exp>>1;base = (base*base) % mod;}return res;}
template <class T> T modinv(T a , T mod){T x , y; egcd<T>(a , mod , x , y);while(x < 0) x += mod; while(x >= mod) x -= mod; return x;}
template <class T> T modinvfermat(T a , T mod){return expo<T>(a , mod - 2 , mod);}
template <class T> bool rev(T a , T b){return a > b;}
template <class T> ll maxpower(T a , T b){ll ans = 0;while(a > 0 && a % b == 0){ans++;a /= b;}return ans;}
template <class T> T mceil(T a, T b){if(a % b == 0) return a/b; else return a/b + 1;}
template <class T> T lcm(T a, T b){return (a)/__gcd<T>(a, b)*(b);}

//const int MOD = (119 << 23) + 1;
const int MOD = 1e9 + 7;
const ll INF = (ll) 1e18;
const double PI = acos(-1);
const double EPS = 1e-9;
const int MAX = 2e9;
const int dx[4] = {+1, 0, -1, 0};
const int dy[4] = {0, +1, 0, -1};
//const int dx[8] = {+1, +1, -1, -1, 0, 0, +1, -1};
//const int dy[8] = {+1, -1, -1, +1, +1, -1, 0, 0};
const int N = 4001;

char a[N][N];
int dist[N][N];
int n, m;

bool isValid(int i, int j) {
	return i >= 0 && j >= 0 && i < n && j < m;
}

int main() {
	io();
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			dist[i][j] = MAX;
			cin >> a[i][j];
		}
	}
	deque<pair<int, int>> q;
	q.push_front({0, 0});
	dist[0][0] = 0;
	while (!q.empty()) {
		int u = q.front().first, v = q.front().second;
		q.pop_front();
		for (int k = 0; k < 4; k++) {
			int r = dx[k] + u;
			int c = dy[k] + v;
			
			if (isValid(r, c) && a[r][c] != '.' && dist[r][c] > dist[u][v] + 1) {
				if (a[r][c] == a[u][v]) {
					dist[r][c] = dist[u][v];
					q.push_front({r, c});
				} else {
					dist[r][c] = dist[u][v] + 1;
					q.push_back({r, c});
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (dist[i][j] != MAX) ans = max(ans, dist[i][j] + 1);
		}
	}
	cout << ans << '\n';
	return 0;
}
/*
5 8
FFR.....
.FRRF...
.RRFFFFF
..RRRFFR
.....FFF

*/

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	5448 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	1 ms	716 KB	Output is correct
4	Correct	10 ms	5164 KB	Output is correct
5	Correct	4 ms	2976 KB	Output is correct
6	Correct	1 ms	448 KB	Output is correct
7	Correct	1 ms	700 KB	Output is correct
8	Correct	1 ms	716 KB	Output is correct
9	Correct	1 ms	1100 KB	Output is correct
10	Correct	4 ms	2508 KB	Output is correct
11	Correct	3 ms	2120 KB	Output is correct
12	Correct	7 ms	3020 KB	Output is correct
13	Correct	4 ms	3020 KB	Output is correct
14	Correct	5 ms	3020 KB	Output is correct
15	Correct	14 ms	5548 KB	Output is correct
16	Correct	15 ms	5432 KB	Output is correct
17	Correct	13 ms	5196 KB	Output is correct
18	Correct	12 ms	5204 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	30796 KB	Output is correct
2	Correct	63 ms	17880 KB	Output is correct
3	Correct	443 ms	94188 KB	Output is correct
4	Correct	138 ms	33604 KB	Output is correct
5	Correct	265 ms	67748 KB	Output is correct
6	Correct	887 ms	108292 KB	Output is correct
7	Correct	16 ms	32204 KB	Output is correct
8	Correct	16 ms	30788 KB	Output is correct
9	Correct	3 ms	588 KB	Output is correct
10	Correct	2 ms	460 KB	Output is correct
11	Correct	16 ms	31596 KB	Output is correct
12	Correct	2 ms	1612 KB	Output is correct
13	Correct	69 ms	17816 KB	Output is correct
14	Correct	37 ms	11844 KB	Output is correct
15	Correct	38 ms	13032 KB	Output is correct
16	Correct	28 ms	6596 KB	Output is correct
17	Correct	161 ms	36060 KB	Output is correct
18	Correct	141 ms	35780 KB	Output is correct
19	Correct	126 ms	33544 KB	Output is correct
20	Correct	103 ms	31012 KB	Output is correct
21	Correct	262 ms	70084 KB	Output is correct
22	Correct	266 ms	67824 KB	Output is correct
23	Correct	309 ms	56764 KB	Output is correct
24	Correct	263 ms	69444 KB	Output is correct
25	Correct	702 ms	94236 KB	Output is correct
26	Correct	598 ms	130888 KB	Output is correct
27	Correct	815 ms	128844 KB	Output is correct
28	Correct	900 ms	108428 KB	Output is correct
29	Correct	899 ms	105720 KB	Output is correct
30	Correct	840 ms	111424 KB	Output is correct
31	Correct	615 ms	73476 KB	Output is correct
32	Correct	727 ms	118520 KB	Output is correct