Submission #1142484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142484		Noproblem29	Virus Experiment (JOI19_virus)	C++20	0 / 100	1 ms	1088 KiB

virus

#include<bits/stdc++.h>
using namespace std;
#ifndef BADGNU
#pragma GCC target("sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#endif
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
#define ll long long
#define int ll
#define ld long double
#define y1 cheza
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int N=805;
const int M=1e5+101;
const int B=447;
const int mod=998244353;
const ll INF=1e18;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
const double eps=1e-6;
int cord(char x){
    if(x=='N'){
        return 0;
    }
    if(x=='S'){
        return 1;
    }
    if(x=='W'){
        return 2;
    }
    if(x=='E'){
        return 3;
    }
    return 4;
}
int n,r,c;
bool check(int x,int y){
    if(x<1||y<1||x>r||y>c)return 0;
    return 1;
}
int s[M];
int u[N][N];
bool mark[N][N];
int dp[(1<<4)];
bool infected(int x,int y){
    if(check(x,y)==0)return 0;
    if(mark[x][y])return 0;
    int mask=0;
    for(int k=0;k<4;k++){
        int i=x-dx[k];
        int j=y-dy[k];
        if(check(i,j)&&mark[i][j]){
            mask|=(1<<k);
        }
    }
    if(u[x][y]<=dp[mask]&&u[x][y]!=0){
        return 1;
    }
    return 0;
}
int calc(int _x,int _y){
    int res=1;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            mark[i][j]=0;
        }
    }
    mark[_x][_y]=1;
    queue<pair<int,int>>q;
    q.push({_x,_y});
    while(q.size()){
        auto [x,y]=q.front();
        q.pop();
        for(int k=0;k<4;k++){
            int i=x+dx[k];
            int j=y+dy[k];
            if(infected(i,j)){
                mark[i][j]=1;
                res++;
                q.push({i,j});
            }
        }
    }
    return res;
}
void test(){
    cin>>n>>r>>c;
    for(int i=1;i<=n;i++){
        char x;
        cin>>x;
        s[i]=cord(x);
        s[i+n]=s[i];
    }
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>u[i][j];
        }
    }
    for(int mask=0;mask<(1<<4);mask++){
        int mx=0;
        for(int i=1;i<=2*n;i++){
            if((mask>>s[i])&1){
                mx++;
            }
            else{
                mx=0;
            }
            dp[mask]=max(dp[mask],mx);
        }
        if(dp[mask]==2*n){
            dp[mask]=1e5;
        }
    }
    int mn=INF;
    int cnt=0;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            if(u[i][j]==0)continue;
            int d=calc(i,j);
            if(d<mn){
                mn=d;
                cnt=0;
            }
            if(d==mn){
                cnt++;
            }
        }
    }
    cout<<mn<<'\n';
    cout<<cnt<<'\n';
}



/*

*/
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // cout.tie(nullptr);
    int t2=1;
    // cin>>t2;
    for(int i=1;i<=t2;i++){
        test();
    }
}

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