Submission #1218485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218485		trantrungkein	Furniture (JOI20_furniture)	C++20	0 / 100	2 ms	2372 KiB

furniture

#include <bits/stdc++.h>
 
#define fi           first 
#define si           second 
#define For(i,a,b)   for (int i = (a), _b =(b); i <= _b; ++i)
#define all(v)       v.begin(), v.end()
#define Unique(v)    v.erase(unique(all(v)), v.end())   
#define MASK(i)      (1LL << (i))
#define bit(i,n)     (((n)>>(i)) & 1)
#define Vii          vector<pair<int,int>>
#define setpr(x)     cout<<setprecision(x)<<fixed
#define Prior        priority_queue< pair<int,int> , Vii, greater<Pair> >
using namespace std;
 
const int Mod = 1E9 + 7;
const long long INF  = 4E18;
const int N = 2e3 + 1;
pair<int,int> par[N][N];
int n,m,vis[N][N],w[N][N],b[N],c[N],a[N][N],ans[N][N],q;
int dx[] {1,0}, dy[] {0,1};
struct node
{
    int u,v,w;
    bool operator < (const node &other) const{
        return w > other.w;
    }
};
bool ok(int i, int j)
{
    return (1 <= i && i <= n && 1 <= j && j <= m && !vis[i][j] && !a[i][j]);
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //freopen("kein.inp","r",stdin);
    //freopen("kein.out","w",stdout);
    cin >> n >> m;
    For(i,1,n) For(j,1,m)
        cin >> a[i][j];
    cin >> q;
    For(i,1,q)
    {
        cin >> b[i] >> c[i];
        w[b[i]][c[i]] = q-i+1;
    }
    priority_queue<node> qer;
    qer.push({1,1,0});
    while(!qer.empty())
    {
        node o = qer.top();qer.pop();
      // if(vis[o.u][o.v]) continue;
   //     cout << o.u <<' ' << o.v <<' ' << w[o.u][o.v] << endl;
  //      cout << par[o.u][o.v].fi  <<' ' <<par[o.u][o.v].si << endl;
     //   vis[o.u][o.v] = 1;
     //   cout << o.u <<' ' <<o.v << endl;
        For(k,0,1)
        {   
            int x = o.u + dx[k], y = o.v + dy[k];
            // cout << x <<' ' << y << "EE" <<endl;
            if(ok(x,y)) qer.push({x,y,w[x][y]}), par[x][y] = {o.u,o.v}, vis[x][y] = 1; 
        }
    }
    int x = n, y = m;
    while(x)
    {   
        ans[x][y] = 1;
        tie(x,y) = par[x][y];
    }
    For(i,1,q)
        cout << !ans[b[i]][c[i]] <<'\n';
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95