oj.uz

Submission #558636

# Submission time Handle Problem Language Result Execution time Memory
558636 2022-05-07T18:51:26 Z groshi Furniture (JOI20_furniture) C++17
100 / 100
 288 ms 22768 KB 
#include<iostream>
#include<vector>
#include<utility>
#include<queue>
using namespace std;
int t[3000][3000];
vector<pair<int,int> > Q;
bool moge[3000][3000];
int ile_o_sumie[6000];
queue<pair<int,int> > kolejka;
void usun(int x,int y)
{
    kolejka.push({x,y});
    moge[x][y]=0;
    while(!kolejka.empty())
    {
        pair<int,int> para=kolejka.front();
        kolejka.pop();
        x=para.first;
        y=para.second;
        ile_o_sumie[x+y]--;
        if(moge[x][y-1]==1 && moge[x+1][y-1]==0)
        {
            moge[x][y-1]=0;
            kolejka.push({x,y-1});
        }
        if(moge[x-1][y]==1 && moge[x-1][y+1]==0)
        {
            moge[x-1][y]=0;
            kolejka.push({x-1,y});
        }
        if(moge[x][y+1]==1 && moge[x-1][y+1]==0)
        {
            moge[x][y+1]=0;
            kolejka.push({x,y+1});
        }
        if(moge[x+1][y]==1 && moge[x+1][y-1]==0)
        {
            moge[x+1][y]=0;
            kolejka.push({x+1,y});
        }
    }
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n,m,x,y,zap;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>t[i][j];
            if(t[i][j]==1)
                Q.push_back({i,j});
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            moge[i][j]=1;
            ile_o_sumie[i+j]++;
        }
    for(int i=0;i<Q.size();i++)
    {
        if(moge[Q[i].first][Q[i].second]==0)
        {
            continue;
        }
        usun(Q[i].first,Q[i].second);
    }
    cin>>zap;
    while(zap--)
    {
        cin>>x>>y;
        if(moge[x][y]==0)
        {
            cout<<"1\n";
            continue;
        }
        if(ile_o_sumie[x+y]==1)
        {
            cout<<"0\n";
            continue;
        }
        usun(x,y);
        cout<<"1\n";
    }
    return 0;
}

Compilation message

furniture.cpp: In function 'int main()':
furniture.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i=0;i<Q.size();i++)
      |                 ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 3 ms 1108 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 4 ms 1108 KB Output is correct
9 Correct 3 ms 1108 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 3 ms 1108 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 4 ms 1108 KB Output is correct
9 Correct 3 ms 1108 KB Output is correct
10 Correct 12 ms 1364 KB Output is correct
11 Correct 2 ms 732 KB Output is correct
12 Correct 122 ms 16076 KB Output is correct
13 Correct 63 ms 13088 KB Output is correct
14 Correct 190 ms 20240 KB Output is correct
15 Correct 204 ms 19764 KB Output is correct
16 Correct 205 ms 21116 KB Output is correct
17 Correct 256 ms 22148 KB Output is correct
18 Correct 214 ms 21632 KB Output is correct
19 Correct 288 ms 22720 KB Output is correct
20 Correct 208 ms 22752 KB Output is correct
21 Correct 246 ms 22768 KB Output is correct