QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#413557#6746. Merge the RectanglesSSHL#TL 95ms18004kbC++146.0kb2024-05-17 18:36:222024-05-17 18:36:23

Judging History

你现在查看的是最新测评结果

  • [2024-05-17 18:36:23]
  • 评测
  • 测评结果:TL
  • 用时:95ms
  • 内存:18004kb
  • [2024-05-17 18:36:22]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 1510;

#define PII pair<int, int>
#define x first
#define y second

int a[N][N];
char sb[N][N], hb[N][N];
int st[N][N], idx;
int n, m;
int maxn = 0;
void bfs(int x, int y)
{
    queue<PII> q;

    st[x][y] = ++idx;
    q.push({x, y});

    while (q.size())
    {
        auto tmp = q.front();
        q.pop();

        // cout << x << ' ' << y << ' ' << tmp.x << ' ' << tmp.y << endl;
        if ((tmp.x - 1) >= 1 && st[tmp.x - 1][tmp.y] == 0 && hb[tmp.x - 1][tmp.y] == '0')
        {
            // cout << x << ' ' << y << ' ' << tmp.x << ' ' << tmp.y << endl;
            q.push({tmp.x - 1, tmp.y});
            st[tmp.x - 1][tmp.y] = st[tmp.x][tmp.y];
        }
        if ((tmp.x + 1) <= n && st[tmp.x + 1][tmp.y] == 0 && hb[tmp.x][tmp.y] == '0')
        {
            // cout << x << ' ' << y << ' ' << tmp.x << ' ' << tmp.y << endl;
            q.push({tmp.x + 1, tmp.y});
            st[tmp.x + 1][tmp.y] = st[tmp.x][tmp.y];
        }
        if ((tmp.y + 1) <= m && st[tmp.x][tmp.y + 1] == 0 && sb[tmp.x][tmp.y] == '0')
        {
            // cout << x << ' ' << y << ' ' << tmp.x << ' ' << tmp.y << endl;
            q.push({tmp.x, tmp.y + 1});
            st[tmp.x][tmp.y + 1] = st[tmp.x][tmp.y];
        }
        if ((tmp.y - 1) >= 1 && st[tmp.x][tmp.y - 1] == 0 && sb[tmp.x][tmp.y - 1] == '0')
        {
            // cout << x << ' ' << y << ' ' << tmp.x << ' ' << tmp.y << endl;
            q.push({tmp.x, tmp.y - 1});
            st[tmp.x][tmp.y - 1] = st[tmp.x][tmp.y];
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    for (int i = 1; i < n; i++)
        for (int j = 1; j <= m; j++)
            cin >> hb[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j < m; j++)
            cin >> sb[i][j];

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (!st[i][j])
            {
                bfs(i, j);
            }
        }
    }
    set<int> sss;
    map<int, pair<int, int>> zs, zx, ys, yx;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            // cout << st[i][j] << ' ';

            maxn = max(st[i][j], maxn);
            if (zs[st[i][j]].first > i && zs[st[i][j]].second > j || zs[st[i][j]].first > i && zs[st[i][j]].second == j || zs[st[i][j]].first == i && zs[st[i][j]].second > j || zs[st[i][j]].first == 0)
            {
                zs[st[i][j]] = {i, j};
            }
            if (zx[st[i][j]].first < i || zx[st[i][j]].first == i && zx[st[i][j]].second > j || zx[st[i][j]].first == 0)
            {
                zx[st[i][j]] = {i, j};
            }
            if (ys[st[i][j]].second < j || ys[st[i][j]].first == j && ys[st[i][j]].second > i || ys[st[i][j]].first == 0)
            {
                ys[st[i][j]] = {i, j};
            }
            if (yx[st[i][j]].first < i && yx[st[i][j]].second < j || yx[st[i][j]].first < i && yx[st[i][j]].second == j || yx[st[i][j]].first == i && yx[st[i][j]].second < j || yx[st[i][j]].first == 0)
            {
                yx[st[i][j]] = {i, j};
            }
        }
    }
    int cnt = 0;
    //  for(int i=1;i<=maxn;i++)
    // {
    //     cout<<i<<endl;
    //     cout<<"zs"<<zs[i].first<<" "<<zs[i].second<<endl;
    //     cout<<"zx"<<zx[i].first<<" "<<zx[i].second<<endl;
    //     cout<<"ys"<<ys[i].first<<" "<<ys[i].second<<endl;
    //     cout<<"yx"<<yx[i].first<<" "<<yx[i].second<<endl;
    // }

    // set<pair<int, array<int, 4>>> s;

    // for (int i = 1; i <= idx; i++)
    // {
    //     ;
    // }
    // cout << cnt << endl;
    bool f=1;
    int tmp=maxn;
    while(tmp--)
    {
    for (int i = 1; i <= maxn; i++)
    {
       
        for (int j = 1; j <= maxn; j++)
        {
            // if(zs[i].first==1&&zs[i].second==1&&zx[i].first==n&&zx[i].second==1&&ys[i].first==1&&ys[i].second==n&&yx[i].first==n&&yx[i].second==n)
            // {
            //     f=0;
            //     break;
            // }
            if (i == j || sss.count(j))
            {
                continue;
            }
            if (zs[i].first == ys[j].first && zs[i].second - 1 == ys[j].second && zx[i].first == yx[j].first && zx[i].second - 1 == yx[j].second)
            {
                zs[i].first = zs[j].first;
                zs[i].second = zs[j].second;
                zx[i].first = zx[j].first;
                zx[i].second = zx[j].second;
                sss.insert(j);
                cnt++;
            }
            if (zs[j].first == ys[i].first && zs[j].second - 1 == ys[i].second && zx[j].first == yx[i].first && zx[j].second - 1 == yx[i].second)
            {
                ys[i].first = ys[j].first;
                ys[i].second = ys[j].second;
                yx[i].first = yx[j].first;
                yx[i].second = yx[j].second;
                sss.insert(j);
                cnt++;
            }
            if (zs[i].first - 1 == zx[j].first && zs[i].second == zx[j].second && ys[i].first - 1 == yx[j].first && ys[i].second == yx[j].second)
            {
                zs[i].first = zs[j].first;
                zs[i].second = zs[j].second;
                ys[i].first = ys[j].first;
                ys[i].second = ys[j].second;
                sss.insert(j);
                cnt++;
            }
            if (zs[j].first == zx[i].first + 1 && zs[j].second == zx[i].second && ys[j].first == yx[i].first + 1 && ys[j].second == yx[i].second)
            {
                zx[i].first = zx[j].first;
                zx[i].second = zx[j].second;
                yx[i].first = yx[j].first;
                yx[i].second = yx[j].second;
                sss.insert(j);
                cnt++;
            }
        }
    }
    }
    if(cnt==maxn-1)
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 7600kb

input:

3 4
0000
0111
101
101
110

output:

YES

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 1ms
memory: 7652kb

input:

3 3
110
011
01
11
10

output:

NO

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 95ms
memory: 18004kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #4:

score: -100
Time Limit Exceeded

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:


result: