Submission #230778

#	Time	Username	Problem	Language	Result	Execution time	Memory
230778		walnutwaldo20	Virus Experiment (JOI19_virus)	C++14	20 / 100	671 ms	262148 KiB

virus

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

#define F0R(i, a) for (int i = 0; i < (int)(a); i++)

#define PB push_back
#define MP make_pair
#define F first
#define S second

using namespace std;

typedef pair<int, int> pii;

#define MAXN 640000

string dirchar = "NESW";
int dr[4]{ -1, 0, 1, 0 };
int dc[4]{ 0, 1, 0, -1 };

int m, r, c;
int ss[MAXN];
int depth[MAXN], grouptop[MAXN];
int on[MAXN];
pii dfspar[MAXN];
int maxseq[16];
int u[800][800];
string s;

int par[MAXN];
int nextnode[MAXN];
int lastnode[MAXN];

int codefor(pii loc) {
    return loc.F * c + loc.S;
}

int root(int node) { return (node == par[node]) ? node : par[node] = root(par[node]); }

bool inBounds(pii loc) {
    return loc.F >= 0 && loc.F < r && loc.S >= 0 && loc.S < c && u[loc.F][loc.S] <= 100000;
}

bool infectedby(pii next, int comp) {
    int mask = 0;
    F0R(d, 4) {
        pii indir = MP(next.F + dr[d], next.S + dc[d]);
        if (inBounds(indir) && root(codefor(indir)) == root(comp)) {
            mask |= 1 << d;
        }
    }
    return maxseq[mask] >= u[next.F][next.S];
}

vector<pii> adjToComp(int comp) {
    vector<pii> res;
    for (int curr = comp; curr != -1; curr = nextnode[curr]) {
        pii p = MP(curr / c, curr % c);
        F0R(d, 4) {
            pii next = MP(p.F + dr[d], p.S + dc[d]);
            if (inBounds(next) && root(codefor(next)) != root(comp)) {
                res.PB(next);
            }
        }
    }
    return res;
}

void join(int a, int b, queue<pii>& q) {
    int r1 = root(a), r2 = root(b);
    if (r1 == r2) {
        return;
    }
    if (ss[r1] > ss[r2]) {
        swap(r1, r2);
    }
    vector<pii> adj = adjToComp(r1);
    par[r1] = r2;
    on[r2] += on[r1];
    
    nextnode[lastnode[r2]] = r1;
    lastnode[r2] = lastnode[r1];
    
    for (const pii p : adj) {
        if (root(codefor(p)) != r2 && infectedby(p, r2)) {
            q.push(p);
        }
    }
    if (depth[grouptop[r1]] < depth[grouptop[r2]]) {
        grouptop[r2] = grouptop[r1];
    }
    ss[r2] += ss[r1];
}

void preprocess() {
    s += s;
    F0R(mask, 16) {
        int running = 0;
        F0R(i, s.size()) {
            int dcode = -1;
            F0R(j, 4) if (s[i] == dirchar[j]) {
                dcode = j;
            }
            if ((mask >> dcode) & 1) {
                running++;
            } else {
                running = 0;
            }
            maxseq[mask] = max(maxseq[mask], running);
        }
        if (maxseq[mask] == (int)s.size()) {
            maxseq[mask] = 100000;
        }
    }
}

void addtostack(stack<pii>& comps, stack<queue<pii>>& adjs, pii newloc) {
    int code = codefor(newloc);
    depth[code] = comps.size();
    on[root(code)]++;
    
    comps.push(newloc);
    adjs.push(queue<pii>());
    
    F0R(d, 4) {
        pii next = MP(newloc.F + dr[d], newloc.S + dc[d]);
        if (inBounds(next) && root(codefor(next)) != root(code)) {
            if (infectedby(next, root(code))) {
                adjs.top().push(next);
            }
        }
    }
}

void tarjan(pii startloc) {
    stack<pii> comps;
    stack<queue<pii>> adjs;
    
    addtostack(comps, adjs, startloc);
    
    while (!comps.empty()) {
        if (adjs.top().empty()) {
            on[root(codefor(comps.top()))]--;
            comps.pop();
            adjs.pop();
        } else {
            pii next = adjs.top().front();
            adjs.top().pop();
            if (root(codefor(next)) == root(codefor(comps.top()))) {
                continue;
            }
            if (depth[codefor(next)] != -1) {
                if (on[root(codefor(next))]) {
                    int curr = grouptop[root(codefor(comps.top()))];
                    while (root(curr) != root(codefor(next))) {
                        pii nextup = dfspar[curr];
                        join(curr, codefor(nextup), adjs.top());
                        curr = grouptop[root(codefor(nextup))];
                    }
                }
            } else {
                dfspar[codefor(next)] = comps.top();
                addtostack(comps, adjs, next);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> m >> r >> c;
    cin >> s;
    F0R(i, r) F0R(j, c) {
        cin >> u[i][j];
        if (u[i][j] == 0) {
            u[i][j] = INT_MAX;
        }
    }
    preprocess();
    F0R(i, r) F0R(j, c) if (u[i][j] != INT_MAX) {
        int code = codefor(MP(i, j));
        par[code] = code;
        ss[code] = 1;
        grouptop[code] = code;
        lastnode[code] = code;
        nextnode[code] = -1;
    }
    F0R(i, r) F0R(j, c) depth[codefor(MP(i, j))] = -1;
    F0R(i, r) F0R(j, c) if (u[i][j] != INT_MAX && depth[codefor(MP(i, j))] == -1) {
        tarjan(MP(i, j));
    }
    
    pii res = MP(INT_MAX, 0);
    F0R(i, r) F0R(j, c) if (u[i][j] != INT_MAX) {
        pii loc = MP(i, j);
        if (codefor(loc) == root(codefor(loc))) {
            bool terminal = true;
            for (const pii p : adjToComp(codefor(loc))) {
                if (infectedby(p, codefor(loc))) {
                    terminal = false;
                }
            }
            if (terminal) {
                int curr = ss[codefor(loc)];
                if (curr == res.F) {
                    res.S += curr;
                } else if (curr < res.F) {
                    res = MP(curr, curr);
                }
            }
        }
    }
    cout << res.F << "\n" << res.S << endl;
}

• Subtask 1: 14 / 14
• Subtask 2: 6 / 6
• Subtask 3: 0 / 80