oj.uz

Submission #478978

# Submission time Handle Problem Language Result Execution time Memory
478978 2021-10-09T10:13:16 Z nicolaalexandra Furniture (JOI20_furniture) C++14
5 / 100
 5000 ms 17960 KB 
#include <bits/stdc++.h>
#define DIM 1010
using namespace std;

int a[DIM][DIM],viz[DIM][DIM];
deque <pair<int,int> > c,w;
int n,m,i,j,q,x,y;

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

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

    for (i=0;i<=m+1;i++)
        a[0][i] = a[n+1][i] = 1;
    for (i=1;i<=n;i++)
        a[i][0] = a[i][m+1] = 1;


    c.push_back(make_pair(1,1));
    viz[1][1] = 1;
    while (!c.empty()){
        int i = c.front().first;
        int j = c.front().second;
        c.pop_front();
        if (!a[i][j+1] && !viz[i][j+1]){
            c.push_back(make_pair(i,j+1));
            viz[i][j+1] = 1;
        }
        if (!a[i+1][j] && !viz[i+1][j]){
            c.push_back(make_pair(i+1,j));
            viz[i+1][j] = 1;
        }
    }

    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if (!viz[i][j] && !a[i][j])
                a[i][j] = 1;


    cin>>q;
    for (;q--;){
        cin>>x>>y;

        c.clear(), w.clear();
        c.push_back(make_pair(x,y));
        w.push_back(make_pair(x,y));
        a[x][y] = 1;

        int ok = 1;
        while (!c.empty()){
            int i = c.front().first;
            int j = c.front().second;
            c.pop_front();

            if (i == n && j == m){
                ok = 0;
                break;
            }

            if (!a[i][j+1] && a[i-1][j+1]){
                c.push_back(make_pair(i,j+1));
                w.push_back(make_pair(i,j+1));
                a[i][j+1] = 1;
            }

            if (!a[i+1][j] && a[i+1][j-1]){
                c.push_back(make_pair(i+1,j));
                w.push_back(make_pair(i+1,j));
                a[i+1][j] = 1;
            }

        }

        cout<<ok<<"\n";

        if (!ok){
            /// trb sa demarchez
            for (auto it : w)
                a[it.first][it.second] = 0;
        }

    }


    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 896 KB Output is correct
2 Correct 9 ms 1100 KB Output is correct
3 Correct 10 ms 1104 KB Output is correct
4 Correct 19 ms 1220 KB Output is correct
5 Correct 19 ms 1104 KB Output is correct
6 Correct 23 ms 1216 KB Output is correct
7 Correct 25 ms 1256 KB Output is correct
8 Correct 22 ms 1236 KB Output is correct
9 Correct 27 ms 1232 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 896 KB Output is correct
2 Correct 9 ms 1100 KB Output is correct
3 Correct 10 ms 1104 KB Output is correct
4 Correct 19 ms 1220 KB Output is correct
5 Correct 19 ms 1104 KB Output is correct
6 Correct 23 ms 1216 KB Output is correct
7 Correct 25 ms 1256 KB Output is correct
8 Correct 22 ms 1236 KB Output is correct
9 Correct 27 ms 1232 KB Output is correct
10 Correct 98 ms 1268 KB Output is correct
11 Correct 14 ms 796 KB Output is correct
12 Correct 765 ms 13400 KB Output is correct
13 Correct 163 ms 9820 KB Output is correct
14 Correct 1842 ms 17536 KB Output is correct
15 Correct 2007 ms 17960 KB Output is correct
16 Execution timed out 5066 ms 17364 KB Time limit exceeded
17 Halted 0 ms 0 KB -