oj.uz

Submission #451594

# Submission time Handle Problem Language Result Execution time Memory
451594 2021-08-03T09:28:41 Z jhnah917 Virus Experiment (JOI19_virus) C++14
100 / 100
 1469 ms 29404 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 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

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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 844 KB Output is correct
2 Correct 535 ms 23008 KB Output is correct
3 Correct 721 ms 26620 KB Output is correct
4 Correct 772 ms 24160 KB Output is correct
5 Correct 491 ms 26548 KB Output is correct
6 Correct 12 ms 8220 KB Output is correct
7 Correct 855 ms 24216 KB Output is correct
8 Correct 131 ms 13684 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 736 KB Output is correct
2 Correct 9 ms 716 KB Output is correct
3 Correct 18 ms 792 KB Output is correct
4 Correct 9 ms 716 KB Output is correct
5 Correct 17 ms 760 KB Output is correct
6 Correct 20 ms 1144 KB Output is correct
7 Correct 8 ms 700 KB Output is correct
8 Correct 19 ms 1120 KB Output is correct
9 Correct 10 ms 1028 KB Output is correct
10 Correct 9 ms 716 KB Output is correct
11 Correct 10 ms 1064 KB Output is correct
12 Correct 12 ms 1032 KB Output is correct
13 Correct 19 ms 1160 KB Output is correct
14 Correct 19 ms 1120 KB Output is correct
15 Correct 18 ms 1120 KB Output is correct
16 Correct 19 ms 1208 KB Output is correct
17 Correct 18 ms 1100 KB Output is correct
18 Correct 11 ms 1040 KB Output is correct
19 Correct 19 ms 1124 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 844 KB Output is correct
2 Correct 535 ms 23008 KB Output is correct
3 Correct 721 ms 26620 KB Output is correct
4 Correct 772 ms 24160 KB Output is correct
5 Correct 491 ms 26548 KB Output is correct
6 Correct 12 ms 8220 KB Output is correct
7 Correct 855 ms 24216 KB Output is correct
8 Correct 131 ms 13684 KB Output is correct
9 Correct 9 ms 736 KB Output is correct
10 Correct 9 ms 716 KB Output is correct
11 Correct 18 ms 792 KB Output is correct
12 Correct 9 ms 716 KB Output is correct
13 Correct 17 ms 760 KB Output is correct
14 Correct 20 ms 1144 KB Output is correct
15 Correct 8 ms 700 KB Output is correct
16 Correct 19 ms 1120 KB Output is correct
17 Correct 10 ms 1028 KB Output is correct
18 Correct 9 ms 716 KB Output is correct
19 Correct 10 ms 1064 KB Output is correct
20 Correct 12 ms 1032 KB Output is correct
21 Correct 19 ms 1160 KB Output is correct
22 Correct 19 ms 1120 KB Output is correct
23 Correct 18 ms 1120 KB Output is correct
24 Correct 19 ms 1208 KB Output is correct
25 Correct 18 ms 1100 KB Output is correct
26 Correct 11 ms 1040 KB Output is correct
27 Correct 19 ms 1124 KB Output is correct
28 Correct 1361 ms 29296 KB Output is correct
29 Correct 1364 ms 29404 KB Output is correct
30 Correct 1184 ms 27476 KB Output is correct
31 Correct 1150 ms 25664 KB Output is correct
32 Correct 1188 ms 24700 KB Output is correct
33 Correct 679 ms 24288 KB Output is correct
34 Correct 1434 ms 29380 KB Output is correct
35 Correct 958 ms 22464 KB Output is correct
36 Correct 1173 ms 24664 KB Output is correct
37 Correct 1469 ms 26020 KB Output is correct
38 Correct 1347 ms 29192 KB Output is correct
39 Correct 645 ms 25268 KB Output is correct
40 Correct 739 ms 25368 KB Output is correct
41 Correct 669 ms 24340 KB Output is correct
42 Correct 1281 ms 27380 KB Output is correct
43 Correct 1222 ms 26972 KB Output is correct
44 Correct 141 ms 13744 KB Output is correct