Submission #1016933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016933		Drake	Virus Experiment (JOI19_virus)	C++17	100 / 100	915 ms	15104 KiB

virus

#include<bits/stdc++.h>
using namespace std;
bitset<800*800>vis,alred;
int R,C,res[800][800],cnt[16],dx[4]{-1,1,0,0},dy[4]{0,0,-1,1},cnt1=1e9,num;
inline int I(int x,int y){
    return x*C+y;
}
inline int st(int x,int y){
    if(x<0||x>=R)return 0;
    if(y<0||y>=C)return 0;
    return vis[I(x,y)];
}   
inline int got(int x,int y){
    if(x<0||x>=R)return 0;
    if(y<0||y>=C)return 0;
    if(vis[I(x,y)])return 0;
    int k=0;
    k+=st(x-1,y);
    k+=st(x+1,y)<<1;
    k+=st(x,y+1)<<2;
    k+=st(x,y-1)<<3;
    return vis[I(x,y)]=(cnt[k]>=res[x][y]);
}
void simulate(int x,int y){
    if(res[x][y]==1e9)return;
    vis.reset();
    vis[I(x,y)]=1;
    queue<pair<int,int>>q;
    q.push({x,y});
    int cnt2=1;
    alred[I(x,y)]=1;
    while(q.size()){
        auto[x,y]=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int x2=x+dx[i],y2=y+dy[i];
            if(got(x2,y2)){
                q.push({x2,y2});
                cnt2++;
                if(alred[I(x2,y2)])
                    return;
            }
        }
        if(cnt2>cnt1)return;
    }
    if(cnt2<cnt1)
        cnt1=num=cnt2;
    else num+=cnt2;
}
void preproc(string winds){
    for(int i=0;i<R;i++)
        for(int j=0;j<C;j++) if(res[i][j])
            res[i][j]=min(res[i][j],(int)winds.size());
        else res[i][j]=1e9;
    winds+=winds;
    for(auto&i:winds)
        if(i=='N')
            i=0;
        else if(i=='S')
            i=1;
        else if(i=='E')
            i=2;
        else i=3;
    for(int i=1;i<16;i++){
        int cur=0;
        for(auto x:winds) if(i&1<<x)
            cnt[i]=max(cnt[i],++cur);
        else cur=0;
    }
}
int main(){
    mt19937 rng(142432);
    cin.tie(0)->sync_with_stdio(0);
    string str;
    cin>>str>>R>>C>>str;
    vector<pair<int,int>>v;
    for(int i=0;i<R;i++) for(int j=0;j<C;j++)
        cin>>res[i][j],v.push_back({i,j});
    preproc(str);
    shuffle(v.begin(),v.end(),rng);
    for(auto[i,j]:v)simulate(i,j);
    cout<<cnt1<<'\n'<<num<<'\n';
}

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