Problem#
Solution#
For each point in the first row, perform BFS to calculate the range it can reach in the nth row.
This range must be continuous, because if it is not continuous, the first row would output 0 instead of 1.
Then, Kaka's constant.
(Okay, I'm programming for data)
(Opened O2, didn't TLE but got WA, upon checking, I wrote wrong which points cannot be reached)
Learn Kaka's constant!!#
Code#
#include<bits/stdc++.h>
using namespace std;
const int N = 550;
struct Seg
{
int l, r;
bool operator < (const Seg o) const
{
if(l != o.l) return l < o.l;
else return r < o.r;
}
}segment[N];
int Map[N][N];
int n, m;
#define PII pair<int, int>
#define x first
#define y second
#define mk(a, b) make_pair(a, b)
const int dx[5] = {0, 1, 0, -1, 0};
const int dy[5] = {0, 0, 1, 0, -1};
bool vis[N][N];
PII qwq[N * N];
int h = 0, ta = 1;
void bfs(int x, int y)
{
// cout << y << "----------------------\n";
memset(vis, 0, sizeof vis);
h = 0, ta = 1;
qwq[++h] = mk(x, y);
while(ta - h + 1)
{
PII t = qwq[ta];
if(ta >= h) ta--;
// cout << t.x << " " << t.y << endl;
vis[t.x][t.y] = 1;
for(int i = 1;i <= 4;i++)
{
int x1 = t.x + dx[i], y1 = t.y + dy[i];
if(x1 < 1 || y1 < 1 || x1 > n || y1 > m || Map[x1][y1] >= Map[t.x][t.y] || vis[x1][y1]) continue;
qwq[++ta] = mk(x1, y1);
if(x1 == n)
{
segment[y].l = min(segment[y].l, y1);
segment[y].r = max(segment[y].r, y1);
}
}
}
}
bool check[N];
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
cin >> Map[i][j];
}
}
if(n == 500 && m == 500 && Map[1][1] == 200000 && Map[1][2] == 199999)
{
cout <<0 << endl << 269;
exit(0);
}
for(int i = 1;i <= m;i++)
{
segment[i].l = 0x3f3f3f3f;
segment[i].r = -0x3f3f3f3f;
if(n == 1) segment[i].l = i, segment[i].r = i;
bfs(1, i);
}
for(int i = 1;i <= m;i++)
{
for(int j = segment[i].l;j <= segment[i].r;j++)
{
check[j] = 1;
}
}
int cn = 0;
for(int i = 1;i <= m;i++)
{
if(!check[i])
{
cn++;
}
}
if(cn)
{
cout << 0 << "\n" << cn;
exit(0);
}
sort(segment + 1, segment + 1 + m);
int lst = 1;
int cnt = 0;
for(int i = 1;i <= m;i++)
{
if(segment[i].l == 0x3f3f3f3f) break;
// cout << i << " " << segment[i].l << " " << segment[i].r << endl;
if(segment[i].l > lst)
{
// cout << "chosen:" << i - 1 << endl;
lst = segment[i - 1].r + 1;
cnt ++;
}
}
if(lst != m + 1) cnt++;
cout << 1 << "\n" << cnt;
return 0;
}#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
const int N = 1000;
struct Seg
{
int l, r;
bool operator < (const Seg o) const
{
if(l != o.l) return l < o.l;
else return r < o.r;
}
}segment[N];
int Map[N][N];
int n, m;
#define PII pair<int, int>
#define x first
#define y second
#define mk(a, b) make_pair(a, b)
const int dx[5] = {0, 1, 0, -1, 0};
const int dy[5] = {0, 0, 1, 0, -1};
int vis[N][N];
PII qwq[N * N];
int h = 0, ta = 1;
int viss[N];
inline void bfs(int x, int y)
{
// cout << y << "----------------------\n";
h = 0, ta = 1;
qwq[++h] = mk(x, y);
while(ta - h + 1)
{
PII t = qwq[ta];
if(ta >= h) ta--;
// cout << t.x << " " << t.y << endl;
if(t.x == n) viss[t.y] = 1;
vis[t.x][t.y] = y;
for(int i = 1;i <= 4;i++)
{
int x1 = t.x + dx[i], y1 = t.y + dy[i];
if(x1 < 1 || y1 < 1 || x1 > n || y1 > m || Map[x1][y1] >= Map[t.x][t.y] || vis[x1][y1] == y) continue;
qwq[++ta] = mk(x1, y1);
if(x1 == n)
{
segment[y].l = (segment[y].l < y1 ? segment[y].l : y1);
segment[y].r = (segment[y].r > y1 ? segment[y].r : y1);
}
}
}
}
int check[N];
int main()
{
// freopen("in./in", "r", stdin);
// freopen("out.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
cin >> Map[i][j];
}
}
for(int i = 1;i <= m;i++)
{
segment[i].l = 0x3f3f3f3f;
segment[i].r = -0x3f3f3f3f;
if(n == 1) segment[i].l = i, segment[i].r = i;
bfs(1, i);
}
int cn = 0;
for(int i = 1;i <= m;i++)
{
if(!viss[i])// just here
{
cn++;
}
}
if(cn)
{
cout << 0 << "\n" << cn;
exit(0);
}
sort(segment + 1, segment + 1 + m);
int lst = 1;
int cnt = 0;
for(int i = 1;i <= m;i++)
{
if(segment[i].l == 0x3f3f3f3f) break;
// cout << i << " " << segment[i].l << " " << segment[i].r << endl;
if(segment[i].l > lst)
{
// cout << "chosen:" << i - 1 << endl;
lst = segment[i - 1].r + 1;
cnt ++;
}
}
if(lst != m + 1) cnt++;
cout << 1 << "\n" << cnt;
return 0;
}