oj.uz

Submission #451576

# Submission time Handle Problem Language Result Execution time Memory
451576 2021-08-03T09:16:05 Z jhnah917 Virus Experiment (JOI19_virus) C++14
6 / 100
 2000 ms 16352 KB 
/******************************
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

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.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1400 KB Output is correct
2 Execution timed out 2082 ms 16352 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1308 KB Output is correct
2 Correct 12 ms 1464 KB Output is correct
3 Correct 22 ms 1460 KB Output is correct
4 Correct 12 ms 1460 KB Output is correct
5 Correct 18 ms 1428 KB Output is correct
6 Correct 297 ms 1824 KB Output is correct
7 Correct 11 ms 1216 KB Output is correct
8 Correct 21 ms 1716 KB Output is correct
9 Correct 196 ms 1540 KB Output is correct
10 Correct 12 ms 1464 KB Output is correct
11 Correct 81 ms 1640 KB Output is correct
12 Correct 461 ms 1632 KB Output is correct
13 Correct 200 ms 1820 KB Output is correct
14 Correct 207 ms 1820 KB Output is correct
15 Correct 192 ms 1732 KB Output is correct
16 Correct 179 ms 1828 KB Output is correct
17 Correct 86 ms 1672 KB Output is correct
18 Correct 93 ms 1644 KB Output is correct
19 Correct 78 ms 1832 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1400 KB Output is correct
2 Execution timed out 2082 ms 16352 KB Time limit exceeded
3 Halted 0 ms 0 KB -