제출 #1145605

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1145605		hirayuu_oj	바이러스 (JOI19_virus)	C++20	14 / 100	185 ms	90616 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;
    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: 0 / 6
• Subtask 3: 0 / 80