oj.uz

Submission #695458

# Submission time Handle Problem Language Result Execution time Memory
695458 2023-02-05T05:44:14 Z baokhue232005 Furniture (JOI20_furniture) C++14
100 / 100
 408 ms 20864 KB 
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
// lethal option

#include<bits/stdc++.h>
using namespace std;

#define all(flg) flg.begin(), flg.end()
#define int long long
#define pb push_back
#define fi first
#define se second
#define endl "\n"
#define eb emplace_back
#define ii pair<int, int>
#define vi vector<int>
#define PI 3.141592653589793238462643383279502884
#define ll long long
#define ld long double
#define for1(i, ff, gg) for(int i = ff; i <= gg; ++i)
#define for2(i, ff, gg) for(int i = ff; i >= gg; --i)
const ll mod = 1e9 + 7;
const int maxN = 3005;
const ll oo = 1e18 + 7;
int n, a[maxN];
int x, y, z, k, m;

int ct[maxN * 5];
bool wall[maxN][maxN];

void comp(int i, int j){
    queue<ii> q;
    q.push(ii(i, j));
    while(!q.empty()){
        ii pr = q.front();
        q.pop();
        x = pr.fi;
        y = pr.se;
        if(wall[x][y]) continue;
        wall[x][y] = 1;
        --ct[x + y];
        if(wall[x - 1][y + 1]){
            q.push(ii(x - 1, y));
            q.push(ii(x, y + 1));
        }
        if(wall[x + 1][y - 1]){
            q.push(ii(x + 1, y));
            q.push(ii(x, y - 1));
        }
    }
}

signed main(){
    // freopen(".inp", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    memset(ct, 0, sizeof(ct));
    memset(wall, 1, sizeof(wall));
    for1(i, 1, n) for1(j, 1, m){
        ++ct[i + j];
        wall[i][j] = 0;
    }
    for1(i, 1, n) for1(j, 1, m){
        char c; cin >> c; if(c == '1') comp(i, j);
    }
    int o; cin >> o; while(o--){
        int x, y; cin >> x >> y;
        if(wall[x][y] || ct[x + y] > 1){
            cout << 1;
            comp(x, y);
        }
        else cout << 0;
        cout << endl;
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9280 KB Output is correct
2 Correct 7 ms 9300 KB Output is correct
3 Correct 7 ms 9280 KB Output is correct
4 Correct 10 ms 9360 KB Output is correct
5 Correct 7 ms 9300 KB Output is correct
6 Correct 7 ms 9304 KB Output is correct
7 Correct 7 ms 9300 KB Output is correct
8 Correct 10 ms 9324 KB Output is correct
9 Correct 9 ms 9284 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9280 KB Output is correct
2 Correct 7 ms 9300 KB Output is correct
3 Correct 7 ms 9280 KB Output is correct
4 Correct 10 ms 9360 KB Output is correct
5 Correct 7 ms 9300 KB Output is correct
6 Correct 7 ms 9304 KB Output is correct
7 Correct 7 ms 9300 KB Output is correct
8 Correct 10 ms 9324 KB Output is correct
9 Correct 9 ms 9284 KB Output is correct
10 Correct 13 ms 9556 KB Output is correct
11 Correct 6 ms 9300 KB Output is correct
12 Correct 140 ms 13856 KB Output is correct
13 Correct 48 ms 11088 KB Output is correct
14 Correct 271 ms 18748 KB Output is correct
15 Correct 313 ms 18972 KB Output is correct
16 Correct 295 ms 19844 KB Output is correct
17 Correct 313 ms 20400 KB Output is correct
18 Correct 388 ms 20196 KB Output is correct
19 Correct 323 ms 20824 KB Output is correct
20 Correct 347 ms 20768 KB Output is correct
21 Correct 408 ms 20864 KB Output is correct