oj.uz

Submission #735144

# Submission time Handle Problem Language Result Execution time Memory
735144 2023-05-03T15:42:23 Z alexdd Furniture (JOI20_furniture) C++17
100 / 100
 278 ms 24840 KB 
#include<bits/stdc++.h>
using namespace std;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int n,m;
vector<pair<bool,pair<int,int>>> updates;
bool tr[1005][1005];///tr[i][j] = 0, daca exista cel putin un drum care trece prin pozitia (i,j)
int cnt[2005];
void completeaza(int x, int y, bool spec)
{
    if(tr[x][y] || (x==1 && y==1) || (x==n && y==m))
        return;
    if(spec || (tr[x-1][y] && tr[x][y-1]) || (tr[x+1][y] && tr[x][y+1]))
    {
        //cout<<x<<" "<<y<<"  "<<spec<<"\n";
        tr[x][y]=1;
        cnt[x+y]--;
        for(int i=0;i<4;i++)
            if(!tr[x+dx[i]][y+dy[i]])
                completeaza(x+dx[i],y+dy[i],0);
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int a,b;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        tr[i][0]=tr[i][m+1]=1;
        for(int j=1;j<=m;j++)
        {
            cin>>a;
            if(a==1)
            {
                updates.push_back({0,{i,j}});
            }
            tr[i][j]=0;
            tr[0][j]=tr[n+1][j]=1;
            cnt[i+j]++;
        }
    }
    int cntq;
    cin>>cntq;
    for(int i=0;i<cntq;i++)
    {
        cin>>a>>b;
        updates.push_back({1,{a,b}});
    }
    for(int i=0;i<updates.size();i++)
    {
        a = updates[i].second.first;
        b = updates[i].second.second;
        int rez;
        if(tr[a][b]==0)///daca exista cel putin un drum care trece
        {
            if(cnt[a+b]>1)
            {
                completeaza(a,b,1);
                rez=1;
            }
            else
            {
                rez=0;
            }
        }
        else
        {
            rez=1;
        }
        if(updates[i].first)
        {
            cout<<rez<<"\n";
            ///afisare
        }
    }
    return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 3 ms 728 KB Output is correct
6 Correct 4 ms 788 KB Output is correct
7 Correct 3 ms 788 KB Output is correct
8 Correct 4 ms 792 KB Output is correct
9 Correct 3 ms 788 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 3 ms 728 KB Output is correct
6 Correct 4 ms 788 KB Output is correct
7 Correct 3 ms 788 KB Output is correct
8 Correct 4 ms 792 KB Output is correct
9 Correct 3 ms 788 KB Output is correct
10 Correct 10 ms 1208 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 131 ms 11060 KB Output is correct
13 Correct 56 ms 4648 KB Output is correct
14 Correct 251 ms 20884 KB Output is correct
15 Correct 234 ms 21040 KB Output is correct
16 Correct 250 ms 22780 KB Output is correct
17 Correct 278 ms 23948 KB Output is correct
18 Correct 253 ms 23380 KB Output is correct
19 Correct 259 ms 24764 KB Output is correct
20 Correct 274 ms 24840 KB Output is correct
21 Correct 266 ms 24752 KB Output is correct