Submission #230749

#	Time	Username	Problem	Language	Result	Execution time	Memory
230749		walnutwaldo20	Virus Experiment (JOI19_virus)	C++14	6 / 100	2087 ms	53888 KiB

virus

#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;
bool vis[MAXN];
int on[MAXN];
pii dfspar[MAXN];
int maxseq[16];
int u[800][800];
string s;

int par[MAXN];
vector<pii> nodesin[MAXN];

bool debug = false;

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

int root(int node) { return (node == par[node]) ? 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 (const pii p : nodesin[comp]) {
        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 printcomp(int compid) {
    /*
    if (!debug) {
        return;
    }
    cout << "contents of component " << compid << ":";
    for (const pii p : nodesin[compid]) {
        cout << " (" << p.F << ", " << p.S << ")";
    }
    cout << endl;*/
}

void join(int a, int b, queue<pii>& q) {
    int r1 = root(a), r2 = root(b);
    if (r1 == r2) {
        return;
    }
    
    /*
    if (debug) {
        cout << "merging comp " << r1 << " with " << r2 << endl;
        printcomp(r1);
        printcomp(r2);
    }*/
    if (nodesin[r1].size() > nodesin[r2].size()) {
        swap(r1, r2);
    }
    vector<pii> adj = adjToComp(r1);
    par[r1] = r2;
    on[r2] += on[r1];
    for (const pii p : nodesin[r1]) {
        nodesin[r2].PB(p);
    }
    for (const pii p : adj) {
        if (root(codefor(p)) != r2 && infectedby(p, r2)) {
            /*
            if (debug) {
                cout << "adding " << p.F << " " << p.S << " to queue" << endl;
            }*/
            q.push(p);
        }
    }
    
    /*
    if (debug) {
        cout << "merged " << r1 << " into " << r2 << endl;
        printcomp(r2);
    }*/
}

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;
        }
        if (debug) {
            F0R(j, 4) if ((mask >> j) & 1) {
                cout << dirchar[j];
            }
            cout << ": " << maxseq[mask] << endl;
        }
    }
}

void tarjan(pii loc) {
    vis[codefor(loc)] = true;
    on[root(codefor(loc))]++;
    
    if (debug) {
        cout << "** dfs on loc " << loc.F << " " << loc.S << endl;
        int compid = root(codefor(loc));
        printf("in comp %d\n", compid);
        printcomp(compid);
    }
    
    queue<pii> tosearch;
    F0R(d, 4) {
        pii next = MP(loc.F + dr[d], loc.S + dc[d]);
        if (!inBounds(next)) {
            continue;
        }
        if (root(codefor(next)) != root(codefor(loc))) {
            if (infectedby(next, root(codefor(loc)))) {
                tosearch.push(next);
            }
        }
    }
    while (!tosearch.empty()) {
        pii next = tosearch.front();
        tosearch.pop();
        if (debug) {
            cout << "trying " << next.F << " " << next.S << endl;
        }
        if (root(codefor(next)) == root(codefor(loc))) {
            if (debug) {
                cout << "location is in the same component" << endl;
            }
            continue;
        }
        if (vis[codefor(next)]) {
            if (on[root(codefor(next))]) {
                pii curr = loc;
                while (root(codefor(curr)) != root(codefor(next))) {
                    pii nextup = dfspar[codefor(curr)];
                    join(codefor(curr), codefor(nextup), tosearch);
                    curr = nextup;
                }
            } else {
                continue;
            }
        } else {
            dfspar[codefor(next)] = loc;
            tarjan(next);
        }
    }
    if (debug) {
        cout << "leaving dfs of (" << loc.F << ", " << loc.S << ")" << endl;
    }
    on[root(codefor(loc))]--;
}

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;
        nodesin[code].PB(MP(i, j));
    }
    F0R(i, r) F0R(j, c) if (u[i][j] != INT_MAX && !vis[codefor(MP(i, j))]) {
        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 = nodesin[codefor(loc)].size();
                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: 0 / 14
• Subtask 2: 6 / 6
• Subtask 3: 0 / 80