oj.uz

Submission #366179

# Submission time Handle Problem Language Result Execution time Memory
366179 2021-02-13T12:49:41 Z wildturtle Furniture (JOI20_furniture) C++14
100 / 100
 3914 ms 325344 KB 
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,i,e,f,g,n,m,k,l,t;
long long A[1003][1003],fix[1000006],fix1[1000006],D[1000006],B[1000006];
set <long long> in[1000006],out[1000006];
void dfs(long long x,long long don) {
    if(fix[x]==1) return;
    fix[x]=1;
    D[x]=don;
    if(x==n*m) { fix1[x]=1; }
    for(auto to : out[x]) {
        dfs(to,don+1);
        if(fix1[to]==1) fix1[x]=1;
    }
    B[don]+=fix1[x];
}
void go_down(long long x,long long y) {
    in[x].erase(y);
    if(in[x].size()==1) return;
    B[D[x]]--;
    fix1[x]=0;
    for(auto to : out[x]) {
        go_down(to,x);
    }
}
void go_up(long long x,long long y) {
    out[x].erase(y);
    if(out[x].size()==1) return;
    B[D[x]]--;
    fix1[x]=0;
    for(auto to : in[x]) {
        go_up(to,x);
    }
}
int main() {
    cin>>n>>m;
    for(long long i=1;i<=n;i++) {
        for(long long j=1;j<=m;j++) {
            cin>>A[i][j];
        }
    }
    for(long long i=1;i<=n;i++) {
        for(long long j=1;j<=m;j++) {
            if(j+1<=m && A[i][j]==0 && A[i][j+1]==0) {
                in[m*(i-1)+j+1].insert(m*(i-1)+j);
                out[m*(i-1)+j].insert(m*(i-1)+j+1);
            }
            if(i+1<=n && A[i][j]==0 && A[i+1][j]==0) {
                in[m*i+j].insert(m*(i-1)+j);
                out[m*(i-1)+j].insert(m*i+j);
            }   
        }
    }
    dfs(1,0);
    for(long long i=1;i<=n*m;i++) {
        //cout<<fix1[i]<<" "<<D[i]<<" "<<B[D[i]]<<endl;
        if(fix1[i]==0) {
            for(auto to : in[i]) {
                out[to].erase(i);
            }
            for(auto to : out[i]) {
                in[to].erase(i);
            }
        }
    }
    cin>>t;
    while(t--) {
        cin>>a>>b;
        a=(a-1)*m+b;
        if(fix1[a]==0) { cout<<1<<endl; continue; }
        l=0;
        if(B[D[a]+1]>out[a].size()) l=1;
        if(l==0) {
            for(auto to : out[a]) {
                if(in[to].size()==2) { l=1; break; }
            }
        }
        if(l==1) {
            cout<<1<<endl;
            fix1[a]=0; B[D[a]]--;
            for(auto to : out[a]) {
                go_down(to,a);
            }
            for(auto to : in[a]) {
                go_up(to,a);
            }
        }
        else cout<<0<<endl;
    }
}

Compilation message

furniture.cpp: In function 'int main()':
furniture.cpp:72:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::set<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         if(B[D[a]+1]>out[a].size()) l=1;
      |            ~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 95852 KB Output is correct
2 Correct 72 ms 95468 KB Output is correct
3 Correct 84 ms 96256 KB Output is correct
4 Correct 87 ms 96364 KB Output is correct
5 Correct 91 ms 96492 KB Output is correct
6 Correct 95 ms 97004 KB Output is correct
7 Correct 95 ms 97004 KB Output is correct
8 Correct 97 ms 97024 KB Output is correct
9 Correct 96 ms 97004 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 95852 KB Output is correct
2 Correct 72 ms 95468 KB Output is correct
3 Correct 84 ms 96256 KB Output is correct
4 Correct 87 ms 96364 KB Output is correct
5 Correct 91 ms 96492 KB Output is correct
6 Correct 95 ms 97004 KB Output is correct
7 Correct 95 ms 97004 KB Output is correct
8 Correct 97 ms 97024 KB Output is correct
9 Correct 96 ms 97004 KB Output is correct
10 Correct 155 ms 104300 KB Output is correct
11 Correct 90 ms 96620 KB Output is correct
12 Correct 1790 ms 285244 KB Output is correct
13 Correct 614 ms 249212 KB Output is correct
14 Correct 3186 ms 280240 KB Output is correct
15 Correct 3428 ms 290044 KB Output is correct
16 Correct 3356 ms 306728 KB Output is correct
17 Correct 3670 ms 318096 KB Output is correct
18 Correct 3704 ms 312428 KB Output is correct
19 Correct 3763 ms 325344 KB Output is correct
20 Correct 3914 ms 325080 KB Output is correct
21 Correct 3768 ms 325232 KB Output is correct