Submission #677693

#	Time	Username	Problem	Language	Result	Execution time	Memory
677693		benedict0724	Virus Experiment (JOI19_virus)	C++17	0 / 100	12 ms	9016 KiB

virus

#include <iostream>
#include <stack>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cassert>

using namespace std;
typedef long long ll;

int dir[200002], bit[16];
bool visited[802][802];
int pos[802][802], U[802][802];
int M, R, C;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int cnt = 0;

void init()
{
    cnt = 0;
    for(int i=1;i<=M;i++) for(int j=1;j<=C;j++)
    {
        pos[i][j] = 0;
        visited[i][j] = false;
    }
}

void dfs(int x, int y)
{
    visited[x][y] = true;
    cnt++;
    for(int d=0;d<4;d++)
    {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if(nx < 1 || nx > R || ny < 1 || ny > C || U[nx][ny] == 0 || visited[nx][ny]) continue;
        pos[nx][ny] += (1<<d);
        if(U[nx][ny] <= bit[pos[nx][ny]]) dfs(nx, ny);
    }
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> M >> R >> C;
    string D; cin >> D;
    for(int i=0;i<16;i++)
    {
        for(int j=0;j<2*M;j++) dir[j] = 0;
        for(int j=0;j<M;j++)
        {
            if(D[j] == 'N' && (i & 1)) dir[j] = dir[j+M] = 1;
            if(D[j] == 'S' && (i & 2)) dir[j] = dir[j+M] = 1;
            if(D[j] == 'W' && (i & 4)) dir[j] = dir[j+M] = 1;
            if(D[j] == 'E' && (i & 8)) dir[j] = dir[j+M] = 1;
        }
        int now = 0;
        bit[i] = 0;
        for(int j=0;j<2*M;j++)
        {
            if(dir[j] == 1) now++;
            else now = 0;
            bit[i] = max(bit[i], now);
        }
    }
    
    for(int i=1;i<=R;i++) for(int j=1;j<=C;j++) cin >> U[i][j];
    int ans = R * C + 1;
    int ansN = 1;
    for(int i=1;i<=R;i++) for(int j=1;j<=C;j++)
    {
        if(U[i][j] == 0) continue;
        init();
        dfs(i, j);
        if(cnt == ans) ansN++;
        else if(cnt < ans)
        {
            ans = cnt;
            ansN = 1;
        }
    }
    cout << ans << "\n" << ansN << "\n";
}

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