oj.uz

Submission #410598

# Submission time Handle Problem Language Result Execution time Memory
410598 2021-05-23T06:32:31 Z JerryLiu06 Virus Experiment (JOI19_virus) C++17
100 / 100
 316 ms 20928 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using db = long double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define mp make_pair
#define f first
#define s second

#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front
 
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
#define EACH(a, x) for (auto& a : x)

const int MOD = 1e9 + 7;
const int MXM = 1e5 + 10;
const int MXR = 810;
const ll INF = 1e18;

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

// 'N' = 0, 'E' = 1, 'S' = 2, 'W' = 3;

const int DIR[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };

int M, R, C, A[MXR][MXR]; int val[100], S[2 * MXM];

int maxSub[(1 << 4)]; // Maximum substring such that each character belongs to our mask

int numComp, comp[MXR][MXR]; bool vis[MXR][MXR]; int ans[MXR][MXR];

pi par[MXR][MXR];

pi find(int X, int Y) { return par[X][Y] == pi{X, Y} ? pi{X, Y} : (par[X][Y] = find(par[X][Y].f, par[X][Y].s)); }

void onion(int X1, int Y1, int X2, int Y2) { par[X1][Y1] = pi{X2, Y2}; }

// BFS + DSU with a current starting point

bool valid(int X, int Y) { return X >= 0 && X < R && Y >= 0 && Y < C; }

void DSU(int X, int Y) {
    comp[X][Y] = ++numComp; queue<pi> Q; Q.push({X, Y}); vpi seen;

    while (!Q.empty()) {
        pi cur = Q.front(); Q.pop(); seen.pb(cur);

        F0R(i, 4) {
            int nx = cur.f + DIR[i][0]; int ny = cur.s + DIR[i][1]; int MSK = 0;
            
            if (!valid(nx, ny) || A[nx][ny] == 0 || comp[nx][ny] == numComp) continue;

            F0R(j, 4) if (valid(nx + DIR[j][0], ny + DIR[j][1]) && comp[nx + DIR[j][0]][ny + DIR[j][1]] == numComp) MSK |= (1 << j);

            if (A[nx][ny] <= maxSub[MSK]) {
                if (find(cur.f, cur.s) != find(nx, ny)) { // New connected component, guaranteed worse answer
                
                    tie(cur.f, cur.s) = find(cur.f, cur.s); tie(nx, ny) = find(nx, ny);
                    
                    if (vis[nx][ny]) vis[cur.f][cur.s] = true; else onion(cur.f, cur.s, nx, ny); return ; 
                }
                comp[nx][ny] = numComp; Q.push({nx, ny});
            }
        }
    }
    tie(X, Y) = find(X, Y); vis[X][Y] = true; EACH(P, seen) ans[P.f][P.s] = sz(seen);
}

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

    cin >> M >> R >> C; val['N'] = 0, val['E'] = 1, val['S'] = 2, val['W'] = 3;  
    
    F0R(i, M) { char c; cin >> c; S[i] = val[c]; } F0R(i, M) S[i + M] = S[i]; M *= 2; 
    
    F0R(i, R) F0R(j, C) cin >> A[i][j], par[i][j] = pi{i, j};

    F0R(MSK, (1 << 4)) {
        int curLen = 0; F0R(i, M) {
            if (MSK & (1 << S[i])) curLen++, ckmax(maxSub[MSK], curLen); else curLen = 0;
        }
        if (maxSub[MSK] == M) maxSub[MSK] = MOD;
    }
    while (true) {
        bool flag = false;
        
        F0R(i, R) F0R(j, C) {
            if (find(i, j) == pi{i, j} && !vis[i][j] && A[i][j]) DSU(i, j), flag = true;
        }

        if (!flag) break;
    }
    int res = MOD; int cnt = 0;
    
    F0R(i, R) F0R(j, C) if (ans[i][j]) {
        if (ans[i][j] < res) res = ans[i][j], cnt = 1; 

        else if (ans[i][j] == res) cnt++;
    }
    cout << res << "\n" << cnt;
}

Compilation message

virus.cpp: In function 'int main()':
virus.cpp:104:46: warning: array subscript has type 'char' [-Wchar-subscripts]
  104 |     F0R(i, M) { char c; cin >> c; S[i] = val[c]; } F0R(i, M) S[i + M] = S[i]; M *= 2;
      |                                              ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 844 KB Output is correct
2 Correct 175 ms 13604 KB Output is correct
3 Correct 171 ms 17216 KB Output is correct
4 Correct 168 ms 14832 KB Output is correct
5 Correct 180 ms 17364 KB Output is correct
6 Correct 6 ms 9384 KB Output is correct
7 Correct 224 ms 15764 KB Output is correct
8 Correct 84 ms 10952 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 6 ms 1324 KB Output is correct
3 Correct 17 ms 1284 KB Output is correct
4 Correct 6 ms 1264 KB Output is correct
5 Correct 17 ms 1228 KB Output is correct
6 Correct 20 ms 1976 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 17 ms 1868 KB Output is correct
9 Correct 2 ms 844 KB Output is correct
10 Correct 6 ms 1228 KB Output is correct
11 Correct 2 ms 1100 KB Output is correct
12 Correct 2 ms 1100 KB Output is correct
13 Correct 16 ms 1868 KB Output is correct
14 Correct 19 ms 1720 KB Output is correct
15 Correct 17 ms 1716 KB Output is correct
16 Correct 16 ms 1848 KB Output is correct
17 Correct 10 ms 1484 KB Output is correct
18 Correct 3 ms 1100 KB Output is correct
19 Correct 17 ms 1864 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 844 KB Output is correct
2 Correct 175 ms 13604 KB Output is correct
3 Correct 171 ms 17216 KB Output is correct
4 Correct 168 ms 14832 KB Output is correct
5 Correct 180 ms 17364 KB Output is correct
6 Correct 6 ms 9384 KB Output is correct
7 Correct 224 ms 15764 KB Output is correct
8 Correct 84 ms 10952 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 6 ms 1324 KB Output is correct
11 Correct 17 ms 1284 KB Output is correct
12 Correct 6 ms 1264 KB Output is correct
13 Correct 17 ms 1228 KB Output is correct
14 Correct 20 ms 1976 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 17 ms 1868 KB Output is correct
17 Correct 2 ms 844 KB Output is correct
18 Correct 6 ms 1228 KB Output is correct
19 Correct 2 ms 1100 KB Output is correct
20 Correct 2 ms 1100 KB Output is correct
21 Correct 16 ms 1868 KB Output is correct
22 Correct 19 ms 1720 KB Output is correct
23 Correct 17 ms 1716 KB Output is correct
24 Correct 16 ms 1848 KB Output is correct
25 Correct 10 ms 1484 KB Output is correct
26 Correct 3 ms 1100 KB Output is correct
27 Correct 17 ms 1864 KB Output is correct
28 Correct 253 ms 20928 KB Output is correct
29 Correct 150 ms 13252 KB Output is correct
30 Correct 167 ms 12684 KB Output is correct
31 Correct 226 ms 15468 KB Output is correct
32 Correct 217 ms 14716 KB Output is correct
33 Correct 166 ms 14916 KB Output is correct
34 Correct 316 ms 20272 KB Output is correct
35 Correct 178 ms 14896 KB Output is correct
36 Correct 250 ms 15216 KB Output is correct
37 Correct 234 ms 18276 KB Output is correct
38 Correct 234 ms 19968 KB Output is correct
39 Correct 207 ms 16708 KB Output is correct
40 Correct 233 ms 16700 KB Output is correct
41 Correct 140 ms 15360 KB Output is correct
42 Correct 211 ms 19924 KB Output is correct
43 Correct 156 ms 15812 KB Output is correct
44 Correct 86 ms 10860 KB Output is correct