oj.uz

Submission #933247

# Submission time Handle Problem Language Result Execution time Memory
933247 2024-02-25T10:12:39 Z De3b0o Virus Experiment (JOI19_virus) C++14
0 / 100
 2000 ms 4824 KB 
#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];

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;
    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])
        {
            infected[i1][j1]=1;
            q.push({i1+1,j1});
            q.push({i1-1,j1});
            q.push({i1,j1+1});
            q.push({i1,j1-1});
        }
    }
    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];
    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 ; 2*m>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;
    for(int i = 1 ; r>=i ; i++)
    {
        for(int j = 1 ; c>=j ; j++)
        {
            if(a[i][j]==0)
                continue;
            int mn1 = bfs(i,j);
            if(mn==mn1)
                ans++;
            if(mn>mn1)
            {
                ans=1;
                mn=mn1;
                //cout << mn << " " << i << " " << j << "\n";
            }
        }
    }
    cout << mn << "\n" << ans;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct
2 Execution timed out 2055 ms 4824 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 6 ms 860 KB Output is correct
3 Correct 23 ms 860 KB Output is correct
4 Correct 4 ms 856 KB Output is correct
5 Correct 22 ms 856 KB Output is correct
6 Correct 280 ms 1116 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 22 ms 1116 KB Output is correct
9 Correct 113 ms 600 KB Output is correct
10 Correct 4 ms 860 KB Output is correct
11 Correct 10 ms 624 KB Output is correct
12 Incorrect 276 ms 612 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct
2 Execution timed out 2055 ms 4824 KB Time limit exceeded
3 Halted 0 ms 0 KB -