Submission #468990

#	Time	Username	Problem	Language	Result	Execution time	Memory
468990		stefantaga	Virus Experiment (JOI19_virus)	C++14	0 / 100	10 ms	1228 KiB

virus

#include <bits/stdc++.h>

using namespace std;
int n,m,virus[805][805],nr,val[305],a[805][805],i;
char ch;
void reseteaza()
{
    int i,j;
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=m; j++)
        {
            virus[i][j]=0;
        }
    }
}
int dirl[4],dirc[4],v[100005],j,ok[100005],nr1,rasp[100005],numar;
bool interior (int x,int y)
{
    if (1<=x&&x<=n&&1<=y&&y<=m)
    {
        return 1;
    }
    return 0;
}
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
#ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
#endif // HOME
    cin>>nr>>n>>m;
    val['S']=0;
    dirl[0]=1;
    dirc[0]=0;
    val['N']=1;
    dirl[1]=-1;
    dirc[1]=0;
    val['W']=2;
    dirl[2]=0;
    dirc[2]=-1;
    val['E']=3;
    dirl[3]=0;
    dirc[3]=1;
    for (i=1; i<=nr; i++)
    {
        cin>>ch;
        v[i]=val[ch];
    }
    for (i=nr+1;i<=2*nr;i++)
    {
        v[i]=v[i-nr];
    }
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=m; j++)
        {
            cin>>a[i][j];
        }
    }
    for (i=0; i<16; i++)
    {
        for (j=0; j<4; j++)
        {
            ok[j]=0;
            if ((i&(1<<j)))
            {
                ok[j]=1;
            }
        }
        nr1=0;
        for (j=1; j<=2*nr; j++)
        {
            if (ok[v[j]]==1)
            {
                nr1++;
                rasp[i]=max(rasp[i],nr1);
            }
            else
            {
                nr1=0;
            }
        }
    }
    int minim=1000005,nrfin=0;
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=m; j++)
        {
            if (a[i][j]==0)
            {
                continue;
            }
            reseteaza();
            queue <pair <int,int> > q;
            q.push({i,j});
            virus[i][j]=1;
            numar=1;
            while (!q.empty())
            {
                auto acum=q.front();
                q.pop();
                if (virus[acum.first][acum.second]==0&&a[acum.first][acum.second]!=0)
                {
                    for (int t=0; t<16; t++)
                    {
                        if (rasp[t]>=a[acum.first][acum.second])
                        {
                            int ok1=1;
                            for (int k=0; k<4; k++)
                            {
                                if ((t&(1<<k)))
                                {
                                    int x,y;
                                    x=acum.first+dirl[k];
                                    y=acum.second+dirc[k];
                                    if (interior(x,y)==0)
                                    {
                                        ok1=0;
                                        break;
                                    }
                                    if (virus[x][y]==0)
                                    {
                                        ok1=0;
                                    }
                                }
                            }
                            if (ok1==1)
                            {
                                virus[acum.first][acum.second]=1;
                                numar++;
                                break;
                            }
                        }
                    }
                    if (virus[acum.first][acum.second]==1)
                    {
                        for (int k=0;k<4;k++)
                        {
                            int x,y;
                            x=acum.first+dirl[k];
                            y=acum.second+dirc[k];
                            if (interior(x,y)!=0&&virus[x][y]==0)
                            {
                                q.push({x,y});
                            }
                        }
                    }
                }
                else
                if (virus[acum.first][acum.second]==1)
                {
                    for (int k=0;k<4;k++)
                    {
                        int x,y;
                            x=acum.first+dirl[k];
                            y=acum.second+dirc[k];
                            if (interior(x,y)!=0&&virus[x][y]==0)
                            {
                                q.push({x,y});
                            }
                    }
                }
            }
            if (numar<minim)
            {
                minim=numar;
                nrfin=1;
            }
            else
            if (numar==minim)
            {
                nrfin++;
            }
        }
    }
    cout<<minim<<'\n'<<nrfin;
    return 0;
}

Compilation message (stderr)

virus.cpp: In function 'int main()':
virus.cpp:50:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |         v[i]=val[ch];
      |                  ^~

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