Submission #410598

#	Time	Username	Problem	Language	Result	Execution time	Memory
410598		JerryLiu06	Virus Experiment (JOI19_virus)	C++17	100 / 100	316 ms	20928 KiB

virus

#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 (stderr)

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 / 14
• Subtask 2: 6 / 6
• Subtask 3: 80 / 80