Submission #677891

#	Time	Username	Problem	Language	Result	Execution time	Memory
677891		qwerasdfzxcl	Virus Experiment (JOI19_virus)	C++17	6 / 100	2064 ms	6576 KiB

virus

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
constexpr int INF = 1e9+100;
char s[100100];
int L, n, m, a[808][808], mx[16];
int visited[1001000], cnt;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

bool valid(int x, int y){return x>0 && x<=n && y>0 && y<=m;}
int c_to_i(int x, int y){return (x-1)*m + y;}
pair<int, int> i_to_c(int s){return {(s-1)/m+1, (s-1)%m+1};}

bool ok(int x, int y){
    if (!a[x][y]) return 0;

    int msk = 0;
    for (int k=0;k<4;k++){
        int nx = x+dx[k], ny = y+dy[k];
        int np = c_to_i(nx, ny);
        if (valid(nx, ny) && visited[np]) msk |= 1<<k;
    }

    return mx[msk] >= a[x][y];
}

void dfs(int s){
    visited[s] = 1;
    cnt++;
    auto [x, y] = i_to_c(s);

    for (int k=0;k<4;k++){
        int nx = x + dx[k], ny = y + dy[k];
        int np = c_to_i(nx, ny);

        if (!valid(nx, ny)) continue;
        if (!visited[np] && ok(nx, ny)){
            dfs(np);
        }
    }
}

int mp(char x){
    if (x=='N') return 0;
    if (x=='E') return 1;
    if (x=='S') return 2;
    if (x=='W') return 3;
    return -1;
}

void init(int msk){
    vector<pair<int, int>> ran;
    for (int i=1;i<=L;i++){
        int typ = mp(s[i]);
        if (!(msk & (1<<typ))) continue;

        if (ran.empty() || ran.back().second+1 < i) ran.emplace_back(i, i);
        else ran.back().second++;
    }

    if (ran.empty()) mx[msk] = 0;
    else if (ran[0]==make_pair(1, L)) mx[msk] = 1e9;
    else{
        for (auto &[l, r]:ran) mx[msk] = max(mx[msk], r-l+1);
        if (ran.back().second==L && ran[0].first==1){
            mx[msk] = max(mx[msk], ran[0].second+L - ran.back().first + 1);
        }
    }

    //printf(" msk = %d -> %d\n", msk, mx[msk]);
}

int simulate(int sx, int sy){
    int s = c_to_i(sx, sy);
    cnt = 0;
    fill(visited, visited+n*m+1, 0);
    dfs(s);
    return cnt;
}

int main(){
    scanf("%d %d %d", &L, &n, &m);
    scanf("%s", s+1);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) scanf("%d", a[i]+j);
    }

    for (int i=0;i<16;i++) init(i);

    int ans = 1e9, cnt = 1;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) if (a[i][j]){
            int val = simulate(i, j);
            if (ans==val){
                cnt++;
            }
            else if (ans > val){
                ans = val;
                cnt = 1;
            }
        }
    }

    printf("%d\n%d\n", ans, cnt);
    return 0;
}

Compilation message (stderr)

virus.cpp: In function 'int main()':
virus.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     scanf("%d %d %d", &L, &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
virus.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     scanf("%s", s+1);
      |     ~~~~~^~~~~~~~~~~
virus.cpp:86:37: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         for (int j=1;j<=m;j++) scanf("%d", a[i]+j);
      |                                ~~~~~^~~~~~~~~~~~~~

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