joi open 2019 virus (kill me)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

string dumbbbb(int msk) {
    string res = "{";
    if (msk & 1) res += "N";
    if (msk & 2) res += "E";
    if (msk & 4) res += "S";
    if (msk & 8) res += "W";
    res += "}";
    return res;
}

const int inf  = 1e9;
const int MAXM = 100010;
const int MAXR = 810;
const int MAXC = 810;

// N, E, S, W
int dr[4] = {-1,  0,  1,  0};
int dc[4] = { 0,  1,  0, -1};

int M, R, C;

inline int OPP(int d) {
    return (d+2)%4;
}

inline bool inside(int r, int c) {
    return r >= 0 && r < R && c >= 0 && c < C;
}

int U[MAXR][MAXC];
int D[MAXM];
int maxlen[1<<4]; // maximum length of subarray of (cyclic) D this mask is ok for

int bfscalls;
bool infected[MAXR][MAXC];
int timeinfected[MAXR][MAXC];
int lastcheck[MAXR][MAXC];
int cellmask[MAXR][MAXC]; // which neighbours are infected

bool adj[MAXR][MAXC][4];

int dfscalls;
int num[MAXR][MAXC];
int low[MAXR][MAXC];
bool instk[MAXR][MAXC];
vector<pii> stk;

int numscc;
int sccid[MAXR][MAXC];
vector<unordered_set<int>> sccadj;
vector<int> sccsize, subtreesize;
vector<bool> sccvisited;

void getmaskdata() {
    for (int msk = 0; msk < (1<<4); ++msk) {
        maxlen[msk] = 0;
        int curlen = 0;
        for (int i = 0; i < M; ++i) {
            if (msk & D[i]) {
                ++curlen;
            } else {
                curlen = 0;
            }
            maxlen[msk] = max(maxlen[msk], curlen);
        }
        if (curlen > 0) {
            if (curlen == M) { // infinite cycle
                maxlen[msk] = inf;
            } else {
                for (int i = 0; i < M; ++i) {
                    if (msk & D[i]) {
                        ++curlen;
                    } else {
                        break;
                    }
                }
                maxlen[msk] = max(maxlen[msk], curlen);
            }
        }
        // cout << "msk=" << dumbbbb(msk) << " maxlen=" << maxlen[msk] << endl;
    }
}

void bfs_expand(int r, int c, queue<pii>& q) {
    for (int d = 0; d < 4; ++d) {
        int r1 = r + dr[d], c1 = c + dc[d];
        if (!inside(r1, c1)) continue;
        if (lastcheck[r1][c1] < bfscalls) {
            lastcheck[r1][c1] = bfscalls;
            cellmask[r1][c1] = 0;
        }
        if (!(cellmask[r1][c1] & (1 << OPP(d)))) {
            cellmask[r1][c1] |= (1 << OPP(d));
            if (infected[r1][c1] && timeinfected[r][c] == timeinfected[r1][c1]) {
                cout << "(1) r=" << r << " c=" << c << " can visit d=" << dumbbbb(1<<d) << " r1=" << r1 << " c1=" << c1 << "\n";
                adj[r][c][d] = true;
            } else {
                q.emplace(r1, c1);
            }
        }
    }
}

void bfs(int startrow, int startcol) {
    cout << "bfs from (" << startrow << "," << startcol << ")\n";
    ++bfscalls;
    queue<pii> q;
    infected[startrow][startcol] = true;
    timeinfected[startrow][startcol] = bfscalls;
    lastcheck[startrow][startcol] = bfscalls;
    bfs_expand(startrow, startcol, q);
    while (!q.empty()) {
        pii top = q.front();
        q.pop();
        int r = top.first, c = top.second;
        if (U[r][c] != 0 && maxlen[cellmask[r][c]] >= U[r][c]) {
            infected[r][c] = true;
            timeinfected[r][c] = bfscalls;
            cout << "infected (" << r << "," << c << ")\n";
            for (int d = 0; d < 4; ++d) {
                int r1 = r + dr[d], c1 = c + dc[d];
                if (inside(r1, c1) && timeinfected[r1][c1] == timeinfected[r][c] && adj[r1][c1][OPP(d)] == false) {
                    cout << "(2) r=" << r << " c=" << c << " can be visited from d=" << dumbbbb(1<<OPP(d)) << " r1=" << r1 << " c1=" << c1 << "\n";
                    adj[r1][c1][OPP(d)] = true;
                }
            }
            bfs_expand(r, c, q);
        }
    }
}

void tarjan(int r, int c) {
    num[r][c] = low[r][c] = dfscalls++;
    instk[r][c] = true;
    stk.emplace_back(r, c);
    for (int d = 0; d < 4; ++d) {
        if (!adj[r][c][d]) continue;
        int r1 = r + dr[d], c1 = c + dc[d];
        if (num[r1][c1] == -1) {
            tarjan(r1, c1);
        }
        if (instk[r1][c1]) {
            low[r][c] = min(low[r][c], low[r1][c1]);
        }
    }
    if (low[r][c] == num[r][c]) {
        ++numscc;
        int SIZE = 0;
        sccadj.push_back(unordered_set<int>());
        sccvisited.push_back(false);
        cout << "new SCC: ";
        while (true) {
            int r1 = stk.back().first, c1 = stk.back().second;
            stk.pop_back();
            ++SIZE;
            instk[r1][c1] = false;
            sccid[r1][c1] = numscc-1;
            cout << "(" << r1 << "," << c1 << ") ";
            if (r1 == r && c1 == c) {
                break;
            }
        }
        sccsize.push_back(SIZE);
        subtreesize.push_back(SIZE);
        cout << endl;
    }
}

void sccdfs(int u) {
    if (sccvisited[u]) return;
    sccvisited[u] = true;
    for (int v : sccadj[u]) {
        sccdfs(v);
        subtreesize[u] += subtreesize[v];
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int charmap[256];
    charmap['N'] = 0, charmap['E'] = 1, charmap['S'] = 2, charmap['W'] = 3;
    cin >> M >> R >> C;
    for (int i = 0; i < M; ++i) {
        char ch;
        cin >> ch;
        D[i] = (1 << (charmap[(int)ch]));
    }
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            cin >> U[i][j];
//            cout << "i=" << i << " j=" << j << " U=" << U[i][j] << endl;
        }
    }
    getmaskdata();
    memset(infected, false, sizeof(infected));
    memset(lastcheck, 0, sizeof(lastcheck));
    memset(cellmask, 0, sizeof(cellmask));
    memset(adj, false, sizeof(adj));
    bfscalls = 0;
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (U[i][j] != 0 && infected[i][j] == false) {
                bfs(i, j);
            }
        }
    }
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            int m = 0;
            for (int d = 0; d < 4; ++d) if (adj[i][j][d]) m |= (1<<d);
            cout << "i=" << i << " j=" << j << " adj:" << dumbbbb(m) << endl;
        }
    }
    numscc = 0;
    memset(num, -1, sizeof(num));
    memset(instk, false, sizeof(instk));
    dfscalls = 0;
    for (int r = 0; r < R; ++r) {
        for (int c = 0; c < C; ++c) {
            if (U[r][c] != 0 && num[r][c] == -1) {
                tarjan(r, c);
            }
        }
    }
    for (int r = 0; r < R; ++r) {
        for (int c = 0; c < C; ++c) {
            int u = sccid[r][c];
            for (int d = 0; d < 4; ++d) {
                if (!adj[r][c][d]) continue;
                int r1 = r + dr[d], c1 = c + dc[d];
                int v = sccid[r1][c1];
                if (u != v) {
                    sccadj[u].insert(v);
                    cout << "scc edge: " << u << " -> " << v << endl;
                }
            }
        }
    }
    for (int r = 0; r < R; ++r) {
        for (int c = 0; c < C; ++c) {
            cout << sccid[r][c] << ' ';
        }
        cout << endl;
    }
    int minsize = 1e9, cnt = 0;
    for (int u = 0; u < numscc; ++u) {
        sccdfs(u);
        int res = subtreesize[u];
        if (res < minsize) {
            minsize = res;
            cnt = sccsize[u];
        } else if (res == minsize) {
            cnt += sccsize[u];
        }
        cout << "u=" << u << " res=" << res << endl;
    }
    cout << minsize << ' ' << cnt << endl;
}