QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#413571#6746. Merge the RectanglesSSHL#TL 90ms18644kbC++146.1kb2024-05-17 18:58:332024-05-17 18:58:34

Judging History

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

  • [2024-05-17 18:58:34]
  • 评测
  • 测评结果:TL
  • 用时:90ms
  • 内存:18644kb
  • [2024-05-17 18:58:33]
  • 提交

answer

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

#define PII pair<int, int>
#define endl '\n'
#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, maxn;

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);
            }
        }
    }

    map<int, pair<int, int>> zs, zx, ys, yx;
    set<int>sss;
    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 = 0;
    int fff[N]={0};
    while (1)
    {
        int tmp = cnt;
        for (int i = 1; i <= maxn; i++)
        {

            for (int j = 1; j <= maxn; j++)
            {
                if (cnt == maxn - 1)
                {
                    f = 1;
                    goto out;
                }
                if (i == j||fff[j]==1)
                {
                    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;
                    fff[j]=1;
                    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;
                     fff[j]=1;
                    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;
                     fff[j]=1;
                    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;
                     fff[j]=1;
                    cnt++;
                }
            }
        }
        if (tmp == cnt)
        {

            goto out;
        }
    }
out:
    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: 1ms
memory: 7724kb

input:

3 4
0000
0111
101
101
110

output:

YES

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 0ms
memory: 7752kb

input:

3 3
110
011
01
11
10

output:

NO

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 90ms
memory: 18644kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #4:

score: -100
Time Limit Exceeded

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:


result: