Submission #163939

#	Time	Username	Problem	Language	Result	Execution time	Memory
163939		ho94949	Virus Experiment (JOI19_virus)	C++17	14 / 100	597 ms	60672 KiB

virus

#include<bits/stdc++.h>
using namespace std;
int M, R, C;
string D;
int U[802][802];
int f[2][2][2][2];
bool dead[802][802];
int color[802][802];
int ufd[656565];

int minv = 1010101010;
int ans = 0;

int Find(int a)
{
    if(a==ufd[a]) return a;
    return ufd[a] = Find(ufd[a]);
}
void Union(int a, int b)
{
    ufd[Find(b)] = Find(a);
}
static int visv = 1;
int doBFS(int a, int b)
{
    int ans = 0;
    ++visv;
    queue<pair<int, int> > Q;
    Q.emplace(make_pair(a, b));
    while(!Q.empty())
    {
        auto[pa,pb] = Q.front(); Q.pop();
        if(color[pa][pb] == visv) continue;
        color[pa][pb] = visv; ++ans;
        int dx[] = {-1, 0, 1, 0};
        int dy[] = {0, 1, 0, -1};
        //printf("%d %d\n", pa, pb);
        for(int d=0; d<4; ++d)
        {
            int a = pa+dx[d], b = pb+dy[d];
            if(0<=a&&a<R&&0<=b&&b<C)
            {
                if(U[a][b] == 0) continue;
                bool N = a>0  && color[a-1][b] == visv;
                bool S = a<R-1 && color[a+1][b] == visv;
                bool W = b>0 && color[a][b-1] == visv;
                bool E = b<C-1 && color[a][b+1] == visv;
                //printf("%d %d %d %d %d %d\n", a, b, N, S, W, E);
                if(f[N][S][W][E] >= U[a][b])
                {
                    Q.emplace(a, b);
                }
            }
        }
    }
    return ans;
}
void DF(vector<pair<int, int> > stables)
{
    memset(color, 0, sizeof color);
    for(auto [a, b]: stables)
    {
        int res = doBFS(a, b);
        if(minv > res)
        {
            minv = res;
            ans = 0;
        }
        if(minv == res) ans += res;
    }
    cout << minv << endl << ans <<endl;
}
void solve()
{
    vector<vector<pair<int, int> > > V;
    for(int i=0; i<R; ++i)
        for(int j=0; j<C; ++j)
        {
            vector<pair<int, int> > tv;
            if(U[i][j] != 0)
            {
                tv.emplace_back(i, j);
                V.push_back(tv);
            }
        }
    vector<pair<int, int> > stables;
    while(!V.empty())
    {
        volatile int K = V.size();
        vector<bool> deads(K, false);
        for(int i=0; i<K; ++i) ufd[i] = i;
        for(int i=0; i<R; ++i)
        for(int j=0; j<C; ++j)
            dead[i][j] = true;
        for(int i=0; i<K; ++i)
        {
            for(auto [a, b]: V[i])
            {
                assert(0 <= a && a<R&& 0<=b&&b<C);
                dead[a][b] = false;
                color[a][b] = i;
            }
        }

        for(int c=0; c<(int)V.size(); ++c)
        {
            bool isdead = true;
            int inflto = -1;
            int dx[] = {-1, 0, 1, 0};
            int dy[] = {0, 1, 0, -1};
            for(auto [aa, bb]: V[c])
            {
                for(int d=0; d<4; ++d)
                {
                    int a = aa+dx[d], b=bb+dy[d];
                    if(a<0||b<0||a>=R||b>=C) continue;
                    if(U[a][b] == 0) continue;
                    bool N = a>0 && !dead[a-1][b] && color[a-1][b] == c;
                    bool S = a<R-1 &&!dead[a+1][b] && color[a+1][b] == c;
                    bool W = b>0 && !dead[a][b-1] && color[a][b-1] == c;
                    bool E = b<C-1 && !dead[a][b+1] && color[a][b+1] == c;
                    if(f[(int)N][(int)S][(int)W][(int)E] >= U[a][b])
                    {
                        //U[a][b] is infected
                        if(dead[a][b])
                        {
                            isdead = false;
                            break;
                        }
                        if(color[a][b] == c) continue;
                        isdead=false;
                        inflto = color[a][b];
                        break;
                    }
                }
                if(!isdead) break;
            }
            if(isdead)
            {
                assert(V[c].size() > 0);
                stables.push_back(V[c][0]);
                deads[c] = true;
            }
            else
            {
                if(inflto == -1)
                { // dead by others
                    deads[c] = true;
                }
                else
                {
                    //printf("%d %d\n", inflto, c);
                    //printf("%d %d\n", K, inflto);
                    assert(0<= inflto && inflto < K);
                    Union(inflto, c);
                }
            }
        }
        for(int c=0; c<K; ++c)
        {
            if(deads[c]) continue;
            int fc = Find(c);
            if(fc == c) continue;
            for(auto x: V[c]) V[fc].push_back(x);
        }
        vector<vector<pair<int, int> > > nv;
        for(int c=0; c<K; ++c)
        {
            if(deads[c]) continue;
            if(Find(c) == c) nv.push_back(V[c]);
        }
        V = nv;
    }
    DF(stables);
    //cout << "X" <<endl;
}
int main()
{
    cin >> M >> R >> C;
    cin >> D; D += D; D += D;
    for(int i=0; i<R; ++i)
        for(int j=0; j<C; ++j)
        {
            cin >> U[i][j];
            U[i][j] = min(U[i][j], M);
        }
    for(int n=0; n<=1; ++n)
    for(int s=0; s<=1; ++s)
    for(int w=0; w<=1; ++w)
    for(int e=0; e<=1; ++e)
    {
        int v = 0, cnt = 0;
        for(char q: D)
        {
            if(n == 1 && q == 'S' ||
            s == 1 && q == 'N' ||
            w == 1 && q == 'W' ||
            e == 1 && q == 'E') ++cnt;
            else cnt = 0;
            v = max(v, cnt);
        }
        f[n][s][w][e] = v;
    }
    solve();
}

Compilation message (stderr)

virus.cpp: In function 'int main()':
virus.cpp:195:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
             if(n == 1 && q == 'S' ||
                ~~~~~~~^~~~~~~~~~~
virus.cpp:197:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
             w == 1 && q == 'W' ||
             ~~~~~~~^~~~~~~~~~~
virus.cpp:198:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
             e == 1 && q == 'E') ++cnt;
             ~~~~~~~^~~~~~~~~~~

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