oj.uz

Submission #850730

# Submission time Handle Problem Language Result Execution time Memory
850730 2023-09-17T11:07:23 Z oscar1f Furniture (JOI20_furniture) C++17
100 / 100
 237 ms 28060 KB 
#include<bits/stdc++.h>
using namespace std;

const int TAILLE_MAX=1005;
int nbLig,nbCol,nbReq,ligNouv,colNouv;
int val[TAILLE_MAX][TAILLE_MAX];
int dvDeb[TAILLE_MAX][TAILLE_MAX],dvFin[TAILLE_MAX][TAILLE_MAX];
int acces[TAILLE_MAX][TAILLE_MAX];
int nbBon[2*TAILLE_MAX];

void DFS_deb(int lig,int col) {
    if (lig<=nbLig and col<=nbCol and dvDeb[lig][col]==0 and val[lig][col]==0) {
        dvDeb[lig][col]=1;
        DFS_deb(lig+1,col);
        DFS_deb(lig,col+1);
    }
}

void DFS_fin(int lig,int col) {
    if (lig>0 and col>0 and dvFin[lig][col]==0 and val[lig][col]==0) {
        dvFin[lig][col]=1;
        DFS_fin(lig-1,col);
        DFS_fin(lig,col-1);
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbLig>>nbCol;
    for (int i=1;i<=nbLig;i++) {
        for (int j=1;j<=nbCol;j++) {
            cin>>val[i][j];
        }
    }
    DFS_deb(1,1);
    DFS_fin(nbLig,nbCol);
    for (int i=1;i<=nbLig;i++) {
        for (int j=1;j<=nbCol;j++) {
            if (dvDeb[i][j]==1 and dvFin[i][j]==1) {
                acces[i][j]=1;
                nbBon[i+j]++;
            }
        }
    }
    deque<pair<int,int>> enCours;
    int lig,col,longueur;
    cin>>nbReq;
    for (int ireq=0;ireq<nbReq;ireq++) {
        cin>>ligNouv>>colNouv;
        if (acces[ligNouv][colNouv]==0) {
            cout<<1<<"\n";
        }
        else if (nbBon[ligNouv+colNouv]==1) {
            cout<<0<<"\n";
        }
        else {
            cout<<1<<"\n";
            nbBon[ligNouv+colNouv]--;
            acces[ligNouv][colNouv]=0;
            enCours.push_back({ligNouv+1,colNouv});
            enCours.push_back({ligNouv,colNouv+1});
            while (!enCours.empty()) {
                longueur=enCours.size();
                for (int i=0;i<longueur;i++) {
                    lig=enCours.front().first;
                    col=enCours.front().second;
                    enCours.pop_front();
                    if (lig<=nbLig and col<=nbCol and acces[lig][col]==1 and acces[lig-1][col]==0 and acces[lig][col-1]==0) {
                        acces[lig][col]=0;
                        nbBon[lig+col]--;
                        enCours.push_back({lig+1,col});
                        enCours.push_back({lig,col+1});
                    } 
                }
            }
            enCours.push_back({ligNouv-1,colNouv});
            enCours.push_back({ligNouv,colNouv-1});
            while (!enCours.empty()) {
                longueur=enCours.size();
                for (int i=0;i<longueur;i++) {
                    lig=enCours.front().first;
                    col=enCours.front().second;
                    enCours.pop_front();
                    if (lig>0 and col>0 and acces[lig][col]==1 and acces[lig+1][col]==0 and acces[lig][col+1]==0) {
                        acces[lig][col]=0;
                        nbBon[lig+col]--;
                        enCours.push_back({lig-1,col});
                        enCours.push_back({lig,col-1});
                    } 
                }
            }
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Correct 2 ms 5468 KB Output is correct
3 Correct 2 ms 5468 KB Output is correct
4 Correct 3 ms 5468 KB Output is correct
5 Correct 3 ms 5600 KB Output is correct
6 Correct 3 ms 5464 KB Output is correct
7 Correct 3 ms 5624 KB Output is correct
8 Correct 4 ms 5512 KB Output is correct
9 Correct 3 ms 5468 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Correct 2 ms 5468 KB Output is correct
3 Correct 2 ms 5468 KB Output is correct
4 Correct 3 ms 5468 KB Output is correct
5 Correct 3 ms 5600 KB Output is correct
6 Correct 3 ms 5464 KB Output is correct
7 Correct 3 ms 5624 KB Output is correct
8 Correct 4 ms 5512 KB Output is correct
9 Correct 3 ms 5468 KB Output is correct
10 Correct 7 ms 5468 KB Output is correct
11 Correct 3 ms 4956 KB Output is correct
12 Correct 142 ms 20564 KB Output is correct
13 Correct 52 ms 17488 KB Output is correct
14 Correct 188 ms 24800 KB Output is correct
15 Correct 190 ms 25148 KB Output is correct
16 Correct 204 ms 26196 KB Output is correct
17 Correct 213 ms 27348 KB Output is correct
18 Correct 210 ms 26776 KB Output is correct
19 Correct 237 ms 27820 KB Output is correct
20 Correct 208 ms 27732 KB Output is correct
21 Correct 217 ms 28060 KB Output is correct