Submission #933892

#	Time	Username	Problem	Language	Result	Execution time	Memory
933892		De3b0o	Virus Experiment (JOI19_virus)	C++14	6 / 100	2078 ms	9472 KiB

virus

#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define er erase
#define pb push_back
#define ppb pop_back()
#define ph push
#define pp pop()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define sqr 340
#define mod 1000000007
#define mid ((l+r)/2)
#define lc (2*n)
#define rc (2*n+1)

using namespace std;

ll fp(ll x , ll y)
{
    if(y==0)
        return 1;
    ll z = fp(x,y/2);
    if(y&1)
        return z*z*x;
    else
        return z*z;
}

int sqrot(ll x)
{
    int l = 0 , r = INT_MAX;
    while(l<=r)
    {
        if(mid*mid>=x)
            r=mid-1;
        else
            l=mid+1;
    }
    return r+1;
}

ll cel(ll x , ll y)
{
    return x/y + bool(x/y);
}

string tb(ll x)
{
    string s = "";
    while(x>0)
    {
        if(x&1)
            s+='1';
        else
            s+='0';
        x/=2;
    }
    while(s.size()<4)
        s+='0';
    return s;
}

ll fb(string s)
{
    ll x = 0;
    ll c = 1;
    for(int8_t i = 0 ; 60>i ; i++)
    {
        if(s[i]=='1')
            x+=c;
        c*=2;
    }
    return x;
}

int m , r , c;
string d;
int a[809][809];
int b[2][2][2][2];
bool tak[809][809];

int bfs(int i , int j)
{
    queue<pair<int,int>> q;
    q.push({i+1,j});
    q.push({i-1,j});
    q.push({i,j-1});
    q.push({i,j+1});
    bool infected[r+2][c+2];
    memset(infected,0,sizeof(infected));
    infected[i][j]=1;
    bool ge = 0;
    while(!q.empty())
    {
        auto x = q.front();
        q.pop();
        int i1 = x.F;
        int j1 = x.S;
        if(infected[i1][j1]||i1<1||j1<1||i1>r||j1>c||a[i1][j1]==0)
            continue;
        bool l1 = 0 , l2 = 0 , l3 = 0 , l4 = 0;
        if(infected[i1+1][j1])
            l1=1;
        if(infected[i1-1][j1])
            l2=1;
        if(infected[i1][j1+1])
            l3=1;
        if(infected[i1][j1-1])
            l4=1;
        if(b[l1][l2][l3][l4]>=a[i1][j1])
        {
            if(tak[i1][j1])
            {
                ge=1;
                break;
            }
            infected[i1][j1]=1;
            q.push({i1+1,j1});
            q.push({i1-1,j1});
            q.push({i1,j1+1});
            q.push({i1,j1-1});
        }
    }
    if(ge)
        return 1e5;
    int an = 0;
    for(int i2 = 1 ; r>=i2 ; i2++)
        for(int j2 = 1 ; c>=j2 ; j2++)
            if(infected[i2][j2])
                an++;
    return an;
}

int main()
{
    d3
    cin >> m >> r >> c;
    cin >> d;
    for(int i = 1 ; r>=i ; i++)
        for(int j = 1 ; c>=j ; j++)
            cin >> a[i][j];
    while(d.size()<=200000)
        d+=d;
    for(int i = 1 ; 16>=i ; i++)
    {
        string s = tb(i);
        bool l1 = 0 , l2 = 0 , l3 = 0 , l4 = 0;
        if(s[0]=='1')
            l1=1;
        if(s[1]=='1')
            l2=1;
        if(s[2]=='1')
            l3=1;
        if(s[3]=='1')
            l4=1;
        int lon = 0;
        int cur = 0;
        for(int j = 0 ; d.size()>j ; j++)
        {
            if((d[j]=='S'&&l1)||(d[j]=='N'&&l2)||(d[j]=='E'&&l3)||(d[j]=='W'&&l4))
            {
                cur++;
                continue;
            }
            lon=max(lon,cur);
            cur=0;
        }
        lon=max(lon,cur);
        b[l1][l2][l3][l4]=lon;
        //cout << l1 << " " << l2 << " " << l3 << " " << l4 << " " << b[l1][l2][l3][l4] << "\n";
    }
    int mn = 1e8;
    int ans = 0;
    pair<int,int> A[r*c];
    for(int i = 1 ; r>=i ; i++)
        for(int j = 1 ; c>=j ; j++)
            A[(i-1)*c+j-1]={i,j};
    random_shuffle(A,A+r*c);
    for(int i = 0 ; r*c>i ; i++)
    {
        int x = A[i].F;
        int y = A[i].S;
        if(a[x][y]==0)
            continue;
        int mn1 = bfs(x,y);
        if(mn1==mn)
            ans++;
        if(mn1<mn)
        {
            ans=1;
            mn=mn1;
        }
        tak[x][y]=1;
    }
    cout << mn << "\n" << ans*mn;
}

Compilation message (stderr)

virus.cpp: In function 'int main()':
virus.cpp:165:33: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  165 |         for(int j = 0 ; d.size()>j ; j++)
      |                         ~~~~~~~~^~

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