Submission #1145671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145671		hirayuu_oj	Virus Experiment (JOI19_virus)	C++20	20 / 100	345 ms	137416 KiB

virus

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;

void dfs(vector<vector<int>> &gr,vector<int> &memo,int &cnt,int pos){
    memo[pos]=-2;
    for(int i:gr[pos]){
        if(memo[i]==-1)dfs(gr,memo,cnt,i);
    }
    memo[pos]=cnt;
    cnt++;
}
//Sが全部同じ文字のときバケモンじゃない？
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int M,R,C;
    cin>>M>>R>>C;
    string S;
    cin>>S;
    if(R<=50&&C<=50){
        S=S+S;
        vector<vector<int>> U(R,vector<int>(C,0));
        rep(i,R){
            rep(j,C){
                cin>>U[i][j];
            }
        }
        string dir="NWSE";
        vector<ll> mxs(16);
        rep(i,16){
            int cnt=0;
            int mx=0;
            rep(j,M*2){
                bool flg=false;
                rep(k,4){
                    if((i>>k)&1){
                        if(S[j]==dir[k])flg=true;
                    }
                }
                if(flg){
                    cnt++;
                }
                else{
                    cnt=0;
                }
                mx=max(mx,cnt);
            }
            if(cnt==M*2)mx=998244353;
            mxs[i]=mx;
        }
        vector<ll> cnt(R*C+1,0);
        rep(x,R){
            rep(y,C){
                if(U[x][y]==0)continue;
                vector<vector<int>> bm(R,vector<int>(C,0));
                stack<pair<int,int>> st;
                st.push({x,y});
                bm[x][y]=-1;
                while(!st.empty()){
                    ll i,j;
                    tie(i,j)=st.top();
                    st.pop();
                    if(i!=R-1&&bm[i+1][j]!=-1){
                        bm[i+1][j]|=1;
                        if(mxs[bm[i+1][j]]>=U[i+1][j]&&U[i+1][j]!=0){
                            st.push({i+1,j});
                            bm[i+1][j]=-1;
                        }
                    }
                    if(i!=0&&bm[i-1][j]!=-1){
                        bm[i-1][j]|=4;
                        if(mxs[bm[i-1][j]]>=U[i-1][j]&&U[i-1][j]!=0){
                            st.push({i-1,j});
                            bm[i-1][j]=-1;
                        }
                    }
                    if(j!=C-1&&bm[i][j+1]!=-1){
                        bm[i][j+1]|=2;
                        if(mxs[bm[i][j+1]]>=U[i][j+1]&&U[i][j+1]!=0){
                            st.push({i,j+1});
                            bm[i][j+1]=-1;
                        }
                    }
                    if(j!=0&&bm[i][j-1]!=-1){
                        bm[i][j-1]|=8;
                        if(mxs[bm[i][j-1]]>=U[i][j-1]&&U[i][j-1]!=0){
                            st.push({i,j-1});
                            bm[i][j-1]=-1;
                        }
                    }
                }
                ll nc=0;
                rep(i,R){
                    rep(j,C){
                        if(bm[i][j]==-1)nc++;
                    }
                }
                cnt[nc]++;
            }
        }
        rep(i,R*C+1){
            if(cnt[i]!=0){
                cout<<i<<"\n"<<cnt[i]<<"\n";
                break;
            }
        }
    }
    else{
        S=S+S;
        vector<vector<int>> U(R,vector<int>(C,0));
        rep(i,R){
            rep(j,C){
                cin>>U[i][j];
            }
        }
        vector<vector<int>> gr(R*C);
        vector<vector<int>> rev(R*C);
        vector<int> invalid(R*C,0);
        rep(i,R){
            rep(j,C){            
                if(U[i][j]==0){
                    invalid[i*C+j]=1;
                    continue;
                }
            }
        }
        string dir="NWSE";
        rep(i,4){
            int cnt=0;
            int mx=0;
            rep(j,M*2){
                if(S[j]==dir[i]){
                    cnt++;
                }
                else{
                    cnt=0;
                }
                mx=max(mx,cnt);
            }
            if(cnt==M*2)mx=998244353;
            rep(j,R){
                rep(k,C){
                    if(U[j][k]==0){
                        continue;
                    }
                    if(dir[i]=='N'&&j==0)continue;
                    if(dir[i]=='S'&&j==R-1)continue;
                    if(dir[i]=='W'&&k==0)continue;
                    if(dir[i]=='E'&&k==C-1)continue;
                    int nxt=j*C+k;
                    if(dir[i]=='N')nxt-=C;
                    if(dir[i]=='S')nxt+=C;
                    if(dir[i]=='W')nxt-=1;
                    if(dir[i]=='E')nxt+=1;
                    if(invalid[nxt])continue;
                    if(U[j][k]<=mx){
                        gr[nxt].push_back(j*C+k);
                        rev[j*C+k].push_back(nxt);
                    }
                }
            }
        }
        int cnt=0;
        vector<int> memo(R*C,-1);
        rep(i,R*C){
            if(invalid[i])continue;
            if(memo[i]!=-1)continue;
            dfs(gr,memo,cnt,i);
        }
        int scc=0;
        vector<int> grp(R*C,-1);
        vector<pair<int,int>> order;
        rep(i,R*C){
            if(invalid[i])continue;
            order.emplace_back(memo[i],i);
        }
        sort(all(order));reverse(all(order));
        for(auto&[_,i]:order){
            if(grp[i]!=-1)continue;
            stack<int> vert;
            vert.push(i);
            grp[i]=scc;
            while(!vert.empty()){
                int pos=vert.top();
                vert.pop();
                for(auto j:rev[pos]){
                    if(grp[j]==-1){
                        grp[j]=scc;
                        vert.push(j);
                    }
                }
            }
            scc++;
        }
        vector<int> valid(scc,1);
        vector<int> ccnt(scc,0);
        rep(i,R*C){
            if(invalid[i])continue;
            ccnt[grp[i]]++;
            for(int j:gr[i]){
                if(grp[i]!=grp[j])valid[grp[i]]=0;
            }
        }
        int mn=998244353;
        rep(i,scc){
            if(valid[i])mn=min(mn,ccnt[i]);
        }
        cout<<mn<<"\n";
        int ans=0;
        rep(i,scc){
            if(valid[i]&&ccnt[i]==mn)ans+=mn;
        }
        cout<<ans<<"\n";
    }
}

• Subtask 1: 14 / 14
• Subtask 2: 6 / 6
• Subtask 3: 0 / 80