Submission #451594

#	Time	Username	Problem	Language	Result	Execution time	Memory
451594		jhnah917	Virus Experiment (JOI19_virus)	C++14	100 / 100	1469 ms	29404 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 ID[888][888];

int Simulation(int r, int c){
    static bool V[888][888];
    static queue<PII> Delete;
    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;
    while(Delete.size()) V[Delete.front().x][Delete.front().y] = false, Delete.pop();

    int ret = 0;
    queue<PII> q;
    q.emplace(r, c);
    Delete.emplace(r, c);
    V[r][c] = true;
    while(q.size()){
        auto [i,j] = q.front(); q.pop();
        ret++;
        if(ID[i][j] < ID[r][c]) return -1;
        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), Delete.emplace(ni, nj), V[ni][nj] = true;
        }
    }
    return ret;
}

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

    vector<PII> Perm;
    for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) Perm.emplace_back(i, j);
    random_shuffle(Perm.begin(), Perm.end());
    for(int i=0; i<Perm.size(); i++) ID[Perm[i].x][Perm[i].y] = i;

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

Compilation message (stderr)

virus.cpp: In function 'int Simulation(int, int)':
virus.cpp:80:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |         auto [i,j] = q.front(); q.pop();
      |              ^
virus.cpp: In function 'int main()':
virus.cpp:100:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for(int i=0; i<Perm.size(); i++) ID[Perm[i].x][Perm[i].y] = i;
      |                  ~^~~~~~~~~~~~
virus.cpp:103:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |     for(auto [i,j] : Perm){
      |              ^

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