// #pragma GCC optimize("Ofast, unroll-loops, no-stack-protector, fast-math, O3, omit-frame-pointer, inline, avx, avx2, fma")
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) ((int)(x).size()) // size of a container
#define F(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(a, x) memset(a, x, sizeof(a)) // set elements of array to some value
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define REMAX(a, b) (a) = max((a), (b)) // set a to the maximum of a and b
#define REMIN(a, b) (a) = min((a), (b));
#define FOREACH(i, t) for (typeof(t.begin()) i = t.begin(); i != t.end(); i++) // traverse an STL data structure
#define all(c) (c).begin(), (c).end() // handy for function like "sort()"
#define contain(c, x) ((c).find(x) != (c).end())
#define present(c, x) (count(all(c), x)>0)
typedef long long ll; // data types used often, but you don't want to type them time by time
typedef unsigned long long ull;
const long double PI = 3.1415926535897932384626;
const int mod = 1000000007;
#define dbg(var) cerr << #var << " = " << (var) << endl; // for debug
#define pb push_back // for vectors
#define SORT(p) sort(all(p))
#define REVERSE(p) reverse(all(p))
#define onecount __builtin_popcount // count number of 1's in a number
#define highbit(x) (63 - __builtin_clzll(x)) // get the index of the highest bit set
#define lowbit(x) __builtin_ctzll(x) // get the index of the lowest bit set
#define bitcount(x) (__builtin_popcount(x) + __builtin_popcount(x >> 32)) // count number of 1's in a number in O(1) time
#define mid(l, r) ((l) + (((r) - (l)) >> 1))
typedef int elem_t;
template <typename T, typename TT>
ostream &operator<<(ostream &s, pair<T, TT> t) { return s << "(" << t.first << "," << t.second << ")"; }
template <typename T>
ostream &operator<<(ostream &s, vector<T> t){ F(i, SZ(t)) s << t[i] << " ";return s;}
template <typename T>
istream &operator>>(istream &in, vector<T>&e){for(auto&x : e) cin >> x; return in;}
template <typename T, typename TT>
istream &operator>>(istream &in, vector<pair<T, TT>>&e){for(auto&x : e) cin >> x.first >> x.second; return in;}
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll largest_multiple_smaller_than_x(ll a, ll k){ return (k / a) * a;}
ll smallest_multiple_greater_than_x(ll a, ll k){ return ((k + a - 1) / a) * a;}
vector<ll>sieve(ll num){vector<ll>prime;vector<bool>isPrime(num + 1, true);isPrime[0] = isPrime[1] = false;for(int i = 2; i <= num; i++){if(isPrime[i]){prime.push_back(i);for(int j = i * 2; j <= num; j += i) isPrime[j] = false;}}return prime;}
#define int long long
vector<int>primeFactors(int num){vector<int>prime;for(int i = 2; i * i <= num; i++){while(num % i == 0){prime.push_back(i);num /= i;}}{if(num > 1) prime.push_back(num);}return prime;}
bool is_prime(ll num){if(num < 2) return false;for(ll i = 2; i * i <= num; i++){if(num % i == 0) return false;}return true;}
vector<int>binary(ll num){vector<int>binary;while(num){binary.push_back(num % 2); num >>= 1;} reverse(all(binary)); return binary;}
int decimal(vector<ll>binary){ int num = 0; for(int i = 0; i < binary.size(); i++){num += binary[i] * (1 << i);}return num;}
ll factorial(ll num, ll mod = 1e9+7){ ll fact = 1; for(ll i = 1; i <= num; i++) fact = (fact * i) % mod; return fact;}
vector<int> divisors(int n){ vector<int> div; for(int i = 1; i * i <= n; i++){ if(n % i == 0){ div.push_back(i); if(i * i != n) div.push_back(n / i); } } return div; }
ll power(ll x, ll y, ll mod = 1e18+7){ll res = 1; x %= mod; while(y > 0){if(y & 1) res = (res * x) % mod; y >>= 1; x = (x * x) % mod;} return res;}
ll mod_inverse(ll num, ll mod = 1e9+7){ return power(num, mod - 2, mod);}
ll NchooseK(ll n, ll k, ll mod = 1e9+7){ll res = 1; k = min(k, n - k); for(ll i = 0; i < k; i++){ res = (res * (n - i)) % mod; res = (res * mod_inverse(i + 1, mod)) % mod;} return res;}
int n, m;
void dfs(int pari, int parj, int i, int j, vector<string> & a, vector<vector<int>> & color, int cur_color){
if(i < 0 || j < 0 || i >= n || j >= m || a[i][j] == '.' || color[i][j] != 0 || a[i][j] != a[pari][parj]) return;
color[i][j] = cur_color;
for(int x = -1; x <= 1; x++){
for(int y = -1; y <= 1; y++){
if(x * y != 0) continue;
dfs(i, j, i + x, j + y, a, color, cur_color);
}
}
}
void solve(){
cin >> n >> m;
vector<string> a(n); cin >> a;
vector<vector<int>> color(n, vector<int>(m, 0));
int cur_color = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(color[i][j] == 0 && a[i][j] != '.') cur_color++;
dfs(i, j, i, j, a, color, cur_color);
}
}
// for(auto e : color) cout << e << '\n';
vector<set<int>> adj(cur_color + 1);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(a[i][j] == '.') continue;
if(i < n - 1 && a[i + 1][j] != '.' && a[i][j] != a[i + 1][j]){
adj[color[i][j]].insert(color[i + 1][j]);
adj[color[i + 1][j]].insert(color[i][j]);
}
if(j < m - 1 && a[i][j + 1] != '.' && a[i][j] != a[i][j + 1]){
adj[color[i][j]].insert(color[i][j + 1]);
adj[color[i][j + 1]].insert(color[i][j]);
}
}
}
queue<pair<int,int>> Q; Q.push({1, 0});
vector<int> vis(cur_color); vis[1] = 1;
int res = 0;
while(!Q.empty()){
int root = Q.front().first;
int d = Q.front().second;
res = max(res, d);
Q.pop();
for(auto e : adj[root]){
if(vis[e]) continue;
vis[e] = 1;
Q.push({e, d + 1});
}
}
cout << res + 1 << '\n';
}
int32_t main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int TT = 1;
// cin >> TT;
while(TT--){
solve();
}
return 0;
}
Compilation message
tracks.cpp: In function 'long long int decimal(std::vector<long long int>)':
tracks.cpp:46:62: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | int decimal(vector<ll>binary){ int num = 0; for(int i = 0; i < binary.size(); i++){num += binary[i] * (1 << i);}return num;}
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
10068 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Runtime error |
15 ms |
10280 KB |
Execution killed with signal 11 |
| 5 |
Correct |
4 ms |
2648 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 9 |
Correct |
1 ms |
600 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
5 ms |
1884 KB |
Output is correct |
| 12 |
Correct |
13 ms |
4184 KB |
Output is correct |
| 13 |
Correct |
5 ms |
2652 KB |
Output is correct |
| 14 |
Correct |
5 ms |
2652 KB |
Output is correct |
| 15 |
Correct |
25 ms |
9812 KB |
Output is correct |
| 16 |
Correct |
32 ms |
10076 KB |
Output is correct |
| 17 |
Correct |
22 ms |
9052 KB |
Output is correct |
| 18 |
Runtime error |
16 ms |
10328 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
59 ms |
4944 KB |
Execution killed with signal 11 |
| 2 |
Correct |
131 ms |
48956 KB |
Output is correct |
| 3 |
Correct |
588 ms |
388116 KB |
Output is correct |
| 4 |
Incorrect |
177 ms |
77440 KB |
Output isn't correct |
| 5 |
Correct |
877 ms |
758288 KB |
Output is correct |
| 6 |
Correct |
1458 ms |
388692 KB |
Output is correct |
| 7 |
Runtime error |
69 ms |
4688 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
59 ms |
4948 KB |
Execution killed with signal 11 |
| 9 |
Incorrect |
3 ms |
1880 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
1112 KB |
Output isn't correct |
| 11 |
Runtime error |
40 ms |
3532 KB |
Execution killed with signal 11 |
| 12 |
Correct |
2 ms |
2136 KB |
Output is correct |
| 13 |
Correct |
113 ms |
48764 KB |
Output is correct |
| 14 |
Incorrect |
73 ms |
28380 KB |
Output isn't correct |
| 15 |
Correct |
62 ms |
31568 KB |
Output is correct |
| 16 |
Incorrect |
33 ms |
13652 KB |
Output isn't correct |
| 17 |
Correct |
313 ms |
125764 KB |
Output is correct |
| 18 |
Correct |
308 ms |
122392 KB |
Output is correct |
| 19 |
Incorrect |
198 ms |
77640 KB |
Output isn't correct |
| 20 |
Incorrect |
136 ms |
85852 KB |
Output isn't correct |
| 21 |
Runtime error |
439 ms |
442196 KB |
Execution killed with signal 11 |
| 22 |
Correct |
836 ms |
758356 KB |
Output is correct |
| 23 |
Incorrect |
517 ms |
230100 KB |
Output isn't correct |
| 24 |
Runtime error |
526 ms |
608652 KB |
Execution killed with signal 11 |
| 25 |
Correct |
1489 ms |
498896 KB |
Output is correct |
| 26 |
Runtime error |
703 ms |
1048576 KB |
Execution killed with signal 9 |
| 27 |
Runtime error |
716 ms |
1048576 KB |
Execution killed with signal 9 |
| 28 |
Correct |
1529 ms |
385360 KB |
Output is correct |
| 29 |
Correct |
1415 ms |
421204 KB |
Output is correct |
| 30 |
Correct |
1303 ms |
544340 KB |
Output is correct |
| 31 |
Correct |
1677 ms |
392020 KB |
Output is correct |
| 32 |
Correct |
1213 ms |
780884 KB |
Output is correct |
