Submission #933938

# Submission time Handle Problem Language Result Execution time Memory
933938 2024-02-26T15:18:01 Z De3b0o Virus Experiment (JOI19_virus) C++14
6 / 100
2000 ms 10076 KB
#include<bits/stdc++.h>
#define F first
#define S second
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long

using namespace std;

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;
}

int main()
{
    d3
    int m;
    int16_t r,c;
    string d;
    cin >> m >> r >> c;
    cin >> d;
    int a[r+1][c+1];
    int b[2][2][2][2];
    for(int16_t i = 1 ; r>=i ; i++)
        for(int16_t j = 1 ; c>=j ; j++)
        {
            cin >> a[i][j];
            if(a[i][j]==0)
                a[i][j]=1e5+1;
        }
    d+=d;
    for(int8_t 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);
        if(lon==2*m)
            lon=1e5;
        b[l1][l2][l3][l4]=lon;
    }
    int mn = 1e6;
    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};
    bool infected[r+2][c+2];
    bool tak[r+1][c+1];
    memset(tak,0,sizeof(tak));
    for(int iiii = 0 ; r*c>iiii ; iiii++)
    {
        int16_t x = A[iiii].F;
        int16_t y = A[iiii].S;
        if(a[x][y]>1e5)
            continue;
        memset(infected,0,sizeof(infected));
        queue<pair<int16_t,int16_t>> q;
        q.push({x,y});
        bool ge = 0;
        int mn1 = 0;
        while(!q.empty())
        {
            pair<int16_t,int16_t> nod = q.front();
            q.pop();
            if(infected[nod.F][nod.S])
                continue;
            infected[nod.F][nod.S]=1;
            mn1++;
            if(mn1>mn)
                break;
            for(int8_t ii = 0 ; 4>ii ; ii++)
            {
                int16_t xx = nod.F , yy = nod.S;
                if(ii==1)
                    xx++;
                else if(ii==2)
                    xx--;
                else if(ii==3)
                    yy++;
                else
                    yy--;
                if(xx<1||xx>r||yy<1||yy>c||infected[xx][yy])
                    continue;
                bool l1 = 0 , l2 = 0 , l3 = 0 , l4 = 0;
                if(infected[xx+1][yy])
                    l1=1;
                if(infected[xx-1][yy])
                    l2=1;
                if(infected[xx][yy+1])
                    l3=1;
                if(infected[xx][yy-1])
                    l4=1;
                if(b[l1][l2][l3][l4]>=a[xx][yy])
                {
                    if(tak[xx][yy])
                    {
                        ge=1;
                        break;
                    }
                    q.push({xx,yy});
                }
            }
            if(ge)
                break;
        }
        tak[x][y]=1;
        if(ge)
            continue;
        if(mn1==mn)
            ans++;
        if(mn1<mn)
        {
            ans=1;
            mn=mn1;
        }
    }
    cout << mn << "\n" << ans*mn;
}

Compilation message

virus.cpp: In function 'int main()':
virus.cpp:57:33: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |         for(int j = 0 ; d.size()>j ; j++)
      |                         ~~~~~~~~^~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Execution timed out 2057 ms 10076 KB Time limit exceeded
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 22 ms 860 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 22 ms 860 KB Output is correct
6 Correct 22 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 22 ms 860 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 22 ms 892 KB Output is correct
14 Correct 23 ms 892 KB Output is correct
15 Correct 22 ms 860 KB Output is correct
16 Correct 21 ms 892 KB Output is correct
17 Correct 11 ms 604 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 22 ms 1112 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Execution timed out 2057 ms 10076 KB Time limit exceeded
3 Halted 0 ms 0 KB -