https://www.codechef.com/viewsolution/45417621
I have used dfs
int n, m;
scanf("%d %d\n", &n, &m);
char *mat[n];
int visited[10000][10000] = {{0}};
The constraints:
1\le N, M \le 10^5
How do you think the size of the visited matrix will be sufficient for such constraints?
haha, You know one thing just few seconds ago i visited your profile from one of your answers for “How much time to reach 4 star” post. Submitted it with [1000][1000] and got runtime error so tried with [10000][10000] runtime error gone.
Canyou able to figure out what is going wrong? why do i get TLE?
The reason could be this
1 Like
So nice of you man! I just removed the visited array instead marked the visited nodes in the input array itself and magically it removed my TLE. Actually what was wrong? Does using extra memory contribute to TLE?
Here’s your
ACfied Code.
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
int cmp(const void *a, const void *b)
{
return (*(int*)b) - (*(int*)a);
}
void track(int r, int c, char **mat, int **visited, int i, int j, int *count)
{
if(visited[i][j]) return;
*count = *count + 1;
visited[i][j] = 1;
// top
if(i-1 >= 0 && (!visited[i-1][j]) && (mat[i-1][j] == '1')) track(r, c, mat, visited, i-1, j, count);
if(i+1 < r && (!visited[i+1][j]) && (mat[i+1][j] == '1')) track(r, c, mat, visited, i+1, j, count);
if(j-1 >= 0 && (!visited[i][j-1]) && (mat[i][j-1] == '1')) track(r, c, mat, visited, i, j-1, count);
if(j+1 < c && (!visited[i][j+1]) && (mat[i][j+1] == '1')) track(r, c, mat, visited, i, j+1, count);
}
int main(void) {
int t;
scanf("%d", &t);
while(t--){
int n, m;
scanf("%d %d\n", &n, &m);
char **mat = (char **)malloc(sizeof(char *)*n);
int **visited = (int **)malloc(sizeof(int *) * n);
for(int i = 0 ; i < n ; i++)
{
mat[i] = (char*)malloc(m*sizeof(char));
scanf("%s", mat[i]);
visited[i] = (int *)malloc(sizeof(int) * m);
for(int j = 0; j < m; j++) {
visited[i][j] = 0;
}
}
int count = 0, ind = 0, arr[1000001];
for(int i = 0; i < n ; i++)
{
for(int j = 0 ; j < m ; j++)
{
count = 0;
if((!visited[i][j]) && mat[i][j] == '1')
{
track(n, m, mat, visited, i, j, &count);
arr[ind++] = count;
}
}
}
int sum = 0;
qsort(arr, ind, sizeof(int), cmp);
for(int i = 1 ; i < ind ; i ++)
{
if(i % 2 == 1) sum += arr[i];
}
printf("%d\n", sum);
}
return 0;
}
No, your perception is wrong. There was a bug, where you declared a matrix of constant number of rows. Rectifying it, your solution gave AC.
My Solution
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<double, double> pd;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
typedef map<int, int> mapi;
typedef map<ll, ll> mapl;
double eps = 1e-12;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define per(i, a, b) for (int i = a; i > b; i--)
#define repl(i, a, b) for (ll i = a; i < b; i++)
#define perl(i, a, b) for (ll i = a; i > b; i--)
#define maploop(p, i) for (auto i = p.begin(); i != p.end(); i++)
#define Ceil(a, b) (((a % b) == 0) ? (a / b) : ((a / b) + 1))
#define stable [](const auto &a, const auto &b) { return a.fi < b.fi; }
#define memset(a, b) memset(a, b, sizeof(a))
#define printvec(v) \
for (auto x : v) \
cout << x << ' ';
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define INF 2e18
#define FASTIO \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define tsolve(t) \
ll t; \
cin >> t; \
while (t--) \
{ \
solve(); \
}
vector<vector<bool>> vis;
vector<string> s;
int LAND;
vi res;
void Fill(int i, int j, int n, int m, vector<string> &s)
{
if (i < 0 || i >= n || j < 0 || j >= m)
return;
if (s[i][j] == '0')
return;
if (vis[i][j])
return;
vis[i][j] = true;
LAND++;
Fill(i - 1, j, n, m, s);
Fill(i + 1, j, n, m, s);
Fill(i, j - 1, n, m, s);
Fill(i, j + 1, n, m, s);
}
void print(int n, int m)
{
rep(i, 0, n) { printvec(vis[i]) cout << endl; }
}
void cnt(int n, int m, vector<string> &s, int i, int j)
{
rep(i, 0, n)
{
rep(j, 0, m)
{
if (!vis[i][j])
{
if (s[i][j] == '1')
{
LAND = 0;
Fill(i, j, n, m, s);
res.pb(LAND);
}
vis[i][j] = true;
}
}
}
}
// ==================== Solve =====================
void solve()
{
int n, m;
cin >> n >> m;
s.resize(n);
vis.resize(n + 1, vector<bool>(m + 1, 0));
rep(i, 0, n) cin >> s[i];
cnt(n, m, s, 0, 0);
int ans = 0;
sort(all(res));
reverse(all(res));
rep(i, 0, sz(res))
{
if (i & 1)
ans += res[i];
}
cout << ans << endl;
vis.clear();
res.clear();
}
// ================================================
signed main()
{
FASTIO
tsolve(t) return 0;
// solve();
}