oj.uz

Submission #1053132

# Submission time Handle Problem Language Result Execution time Memory
1053132 2024-08-11T09:01:12 Z Zbyszek99 Furniture (JOI20_furniture) C++17
100 / 100
 270 ms 129404 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define size(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
//mt19937 mt;void random(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll rand(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

int n,m;

int dim(int v)
{
    return (v/m) + (v - (v/m)*m); 
}

bool blocked[1000000];
int good[1000000];
bool bad[1000000];
bitset<1000000> odw2;
bitset<1000000> odw;
vector<int> graf1[1000001];
vector<int> graf2[1000001];
int good_on_dim[1000001];

void dfs1(int v)
{
    odw[v] = 1;
    good[v]++;
    forall(it,graf1[v])
    {
        if(odw[it] == 0 && !blocked[it])
        {
            dfs1(it);
        }
    }
}

void dfs2(int v)
{
    odw2[v] = 1;
    good[v]++;
    if(good[v] == 2)
    {
        good_on_dim[dim(v)]++;
        bad[v] = false;
    }
    forall(it,graf2[v])
    {
        if(odw2[it] == 0 && !blocked[it])
        {
            dfs2(it);
        }
    }
}

void dfs_bad(int v, int pocz = -1)
{
    int c_bad = 0;
    int c_bad2 = 0;
    forall(it,graf1[v]) if(bad[it]) c_bad2++;
    forall(it,graf2[v]) if(bad[it]) c_bad++;
    if(c_bad != 2 && c_bad2 != 2 && !(v < m && c_bad == 1) && !(v % m == 0 && c_bad == 1) && !(v > m*n-1-m && c_bad2 == 1) && !(v%m == m-1 && c_bad2== 1)  && v != pocz) return;
   // cout << v << " dfs\n";
    bad[v] = true;
    if(v != pocz) good_on_dim[dim(v)]--;
    forall(it,graf1[v])
    {
        if(!bad[it]) dfs_bad(it);
    }
    forall(it,graf2[v])
    {
        if(!bad[it]) dfs_bad(it);
    }
}

int get_int()
    {
        int x = 0;
        char c = getchar();
        for(;c < '0' || c > '9'; c = getchar());
        for(;c >= '0' && c <= '9'; c = getchar())
        {
            x = 10*x + (c - '0');
        }
        return x;
    }
    

void solve()
{
    n = get_int(); m = get_int();
    rep(i,n) rep(j,m) blocked[i*m+j] = get_int();
    rep(i,n)
    {
        rep(j,m) 
        {
            if(i != n-1)
            {
                graf1[i*m+j].pb((i+1)*m+j);
                graf2[(i+1)*m+j].pb(i*m+j);
            }
            if(j != m-1)
            {
                graf1[i*m+j].pb(i*m+j+1);
                graf2[i*m+j+1].pb(i*m+j);
            }
        }
    }
    //cout << "xd\n";
    dfs1(0);
    rep(i,n*m) bad[i] = true;
    //cout << "xd\n";
    dfs2(n*m-1);
 //   cout << "xd\n";
    int q;
    q = get_int();
 //   rep(i,n*m)
  ///  {
  //      cout << bad[i] << " ";
  //  }
  //  cout << "bad\n";
    rep(i,q)
    {
        int x,y;
        y = get_int(); x = get_int();
        x--;
        y--;
        int v = y*m+x;
     //   cout << v<< " " << bad[v] << " " << dim(v) << " " << size(good_on_dim[dim(v)]) << " d\n";
    //    forall(it,good_on_dim[dim(v)])cout << it << " ";
   //     cout << " dim\n";
        if(bad[v])
        {
            cout << "1\n";
            continue;
        }
        if(good_on_dim[dim(v)] == 1)
        {
            cout << "0\n";
            continue;
        }
        cout << "1\n";
        bad[v] = true;
        good_on_dim[dim(v)]--;
        dfs_bad(v,v);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random();
    int t = 1;
 //   cin >> t;
    while(t--) solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 52060 KB Output is correct
2 Correct 7 ms 52036 KB Output is correct
3 Correct 11 ms 52316 KB Output is correct
4 Correct 10 ms 52344 KB Output is correct
5 Correct 9 ms 52416 KB Output is correct
6 Correct 8 ms 52316 KB Output is correct
7 Correct 10 ms 52316 KB Output is correct
8 Correct 12 ms 52316 KB Output is correct
9 Correct 11 ms 52316 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 52060 KB Output is correct
2 Correct 7 ms 52036 KB Output is correct
3 Correct 11 ms 52316 KB Output is correct
4 Correct 10 ms 52344 KB Output is correct
5 Correct 9 ms 52416 KB Output is correct
6 Correct 8 ms 52316 KB Output is correct
7 Correct 10 ms 52316 KB Output is correct
8 Correct 12 ms 52316 KB Output is correct
9 Correct 11 ms 52316 KB Output is correct
10 Correct 14 ms 55388 KB Output is correct
11 Correct 8 ms 52316 KB Output is correct
12 Correct 237 ms 118668 KB Output is correct
13 Correct 123 ms 111040 KB Output is correct
14 Correct 270 ms 119896 KB Output is correct
15 Correct 250 ms 117132 KB Output is correct
16 Correct 164 ms 122900 KB Output is correct
17 Correct 170 ms 126804 KB Output is correct
18 Correct 231 ms 124980 KB Output is correct
19 Correct 202 ms 129364 KB Output is correct
20 Correct 183 ms 129404 KB Output is correct
21 Correct 191 ms 129364 KB Output is correct