Submission #451576

#	Time	Username	Problem	Language	Result	Execution time	Memory
451576		jhnah917	Virus Experiment (JOI19_virus)	C++14	6 / 100	2082 ms	16352 KiB

virus

/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using PII = pair<int, int>;

// N S W E
constexpr int di[] = {-1, 1, 0, 0};
constexpr int dj[] = {0, 0, -1, 1};

inline int DIR(char c){
    switch(c){
        case 'N': return 0;
        case 'S': return 1;
        case 'W': return 2;
        case 'E': return 3;
        default: return -1;
    }
}

int N, M, U[888][888];
bool A[888][888][16];

void Init(){
    int L, Dead[16] = {0};
    string Pattern, S;
    cin >> L >> N >> M >> Pattern;
    for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) cin >> U[i][j];
    while(S.size() < 200'000) S += Pattern;
    L = S.size();

    for(int i=0; i<16; i++){
        int now = 0;
        for(int j=0; j<L; j++){
            if(i & (1 << DIR(S[j]))) Dead[i] = max(Dead[i], ++now);
            else now = 0;
        }
    }
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            for(int k=0; k<16; k++){
                if(U[i][j] > 0 && U[i][j] <= Dead[k]) A[i][j][k] = true;
            }
        }
    }
}

int Simulation(int r, int c){
    static bool V[888][888];
    static function<int(int,int)> ADJ = [](int i, int j){
        int adj = 0;
        for(int k=0; k<4; k++) if(V[i+di[k]][j+dj[k]]) adj |= 1 << k;
        return adj;
    };

    if(U[r][c] == 0) return 0;
    memset(V, 0, sizeof V);

    int ret = 0;
    queue<PII> q;
    q.emplace(r, c);
    V[r][c] = true;
    while(q.size()){
        auto [i,j] = q.front(); q.pop();
        ret++;
        for(int k=0; k<4; k++){
            int ni = i + di[k], nj = j + dj[k];
            if(ni < 1 || nj < 1 || ni > N || nj > M || V[ni][nj]) continue;
            int adj = ADJ(ni, nj);
            if(A[ni][nj][adj]) q.emplace(ni, nj), V[ni][nj] = true;
        }
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    Init();

    int mn = 0x3f3f3f3f, cnt = 1;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            if(U[i][j] == 0) continue;
            int now = Simulation(i, j);
            if(mn > now) mn = now, cnt = 1;
            else if(mn == now) cnt++;
        }
    }
    cout << mn << "\n" << cnt;
}

Compilation message (stderr)

virus.cpp: In function 'int Simulation(int, int)':
virus.cpp:76:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |         auto [i,j] = q.front(); q.pop();
      |              ^

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