Submission #1005478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005478		De3b0o	Virus Experiment (JOI19_virus)	C++14	100 / 100	619 ms	48412 KiB

virus

#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define ppb pop_back()
#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 mid ((l+r)/2)
#define lc (2*x)
#define rc (2*x+1)

using namespace std;

ll n, m, d;
string s;
ll g[809][809];
bool vis[809][809];
bool vs[809][809];
ll fans[809][809];
ll t[2][2][2][2];
ll mn, ans;
ll cost;
ll timer;

void bfs(ll d1, ll d2, ll o)
{
    queue<pll> q;
    q.push({d1,d2});
    vector<pll> v;
    while(!q.empty())
    {
        auto it = q.front();
        q.pop();
        ll x = it.F, y = it.S;
        if(vis[x][y]||x==0||y==0||x>n||y>m)
            continue;
        vis[x][y]=1;
        v.pb({x,y});
        if(vs[x][y])
        {
            cost=1e18;
            break;
        }
        cost++;
        for(int h = 0 ; 4>h ; h++)
        {
            ll i = x , j = y;
            if(h==1)
                i--;
            else if(h==2)
                i++;
            else if(h)
                j--;
            else
                j++;
            bool l1 , l2 , l3 , l4;
            l1 = l2 = l3 = l4 = 0;
            l1=(i<n&&vis[i+1][j]);
            l2=(i>1&&vis[i-1][j]);
            l3=(j<m&&vis[i][j+1]);
            l4=(j>1&&vis[i][j-1]);
            if(t[l1][l2][l3][l4]>=g[i][j])
                q.push({i,j});
        }
    }
    for(auto it : v)
        vis[it.F][it.S]=0;
    vs[d1][d2]=1;
    fans[d1][d2]=cost;
}

int main()
{
    cin >> d >> n >> m;
    cin >> s;
    for(int i = 1 ; n>=i ; i++)
    {
        for(int j = 1 ; m>=j ; j++)
        {
            cin >> g[i][j];
            if(g[i][j]==0)
                g[i][j]=100001;
        }
    }
    s+=s;
    d+=d;
    for(int h = 0 ; 16>h ; h++)
    {
        ll mx = 0;
        ll c = 0;
        bool l1, l2, l3, l4;
        l1 = l2 = l3 = l4 = 0;
        l1=((1<<0)&h);
        l2=((1<<1)&h);
        l3=((1<<2)&h);
        l4=((1<<3)&h);
        for(int i = 0 ; d>i ; i++)
        {
            if((s[i]=='S'&&l1)||(s[i]=='N'&&l2)||(s[i]=='E'&&l3)||(s[i]=='W'&&l4))
            {
                c++;
                mx=max(mx,c);
            }
            else
                c=0;
        }
        if(mx==d)
            mx=100000;
        t[l1][l2][l3][l4]=mx;
    }
    vector<pll> idx;
    for(int i = 1 ; n>=i ; i++)
        for(int j = 1 ; m>=j ; j++)
            idx.pb({i,j});
    random_shuffle(idx.begin(),idx.end());
    mn=1e18;
    timer=1;
    for(int h = 0 ; idx.size()>h ; h++)
    {
        ll i = idx[h].F;
        ll j = idx[h].S;
        if(g[i][j]==100001)
            continue;
        cost=0;
        ll o = -1;
        if(vis[i][j])
            o=vis[i][j];
        bfs(i,j,o);
        if(mn>cost)
        {
            ans=0;
            mn=cost;
        }
        if(mn==cost)
            ans++;
        timer++;
    }
    cout << mn << "\n" << ans*mn;
}

Compilation message (stderr)

virus.cpp: In function 'int main()':
virus.cpp:125:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |     for(int h = 0 ; idx.size()>h ; h++)
      |                     ~~~~~~~~~~^~

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