oj.uz

Submission #230792

# Submission time Handle Problem Language Result Execution time Memory
230792 2020-05-11T18:49:16 Z walnutwaldo20 Virus Experiment (JOI19_virus) C++14
100 / 100
 610 ms 85128 KB 
#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 memcounter = 0;
int prevmemcounter;

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);
                memcounter += sizeof(next);
            }
        }
    }
    return res;
}

bool adjacentto(pii p, int comp) {
    F0R(d, 4) {
        pii next = MP(p.F + dr[d], p.S + dc[d]);
        if (inBounds(next) && root(codefor(next)) != root(comp)) {
            return true;
        }
    }
    return false;
}

void join(int a, int b, vector<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.PB(p);
            memcounter += sizeof(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;
        }
    }
}

pii comps[MAXN];
vector<pii> adjs[MAXN];
int stacksize = 0;

void addtostack(pii newloc) {
    int code = codefor(newloc);
    depth[code] = stacksize;
    on[root(code)]++;
    
    comps[stacksize++] = newloc;
    
    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[stacksize - 1].PB(next);
                memcounter += sizeof(next);
            }
        }
    }
}

void tarjan(pii startloc) {
    addtostack(startloc);
    
    while (stacksize) {
        pii node = comps[stacksize - 1];
        if (adjs[stacksize - 1].empty()) {
            on[root(codefor(node))]--;
            stacksize--;
        } else {
            pii next = adjs[stacksize - 1].back();
            adjs[stacksize - 1].pop_back();
            if (root(codefor(next)) == root(codefor(node))) {
                continue;
            }
            if (depth[codefor(next)] != -1) {
                if (on[root(codefor(next))]) {
                    int curr = grouptop[root(codefor(node))];
                    while (root(curr) != root(codefor(next))) {
                        pii nextup = dfspar[curr];
                        join(curr, codefor(nextup), adjs[stacksize - 1]);
                        curr = grouptop[root(codefor(nextup))];
                    }
                }
            } else {
                dfspar[codefor(next)] = node;
                addtostack(next);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    memcounter += sizeof(ss);
    memcounter += sizeof(depth);
    memcounter += sizeof(grouptop);
    memcounter += sizeof(on);
    memcounter += sizeof(dfspar);
    memcounter += 800 * 800 * sizeof(int);
    memcounter += sizeof(par);
    memcounter += sizeof(nextnode);
    memcounter += sizeof(lastnode);
    memcounter += sizeof(comps);
    memcounter += sizeof(adjs);
    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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 15744 KB Output is correct
2 Correct 304 ms 40440 KB Output is correct
3 Correct 303 ms 40440 KB Output is correct
4 Correct 266 ms 35448 KB Output is correct
5 Correct 300 ms 35704 KB Output is correct
6 Correct 14 ms 17920 KB Output is correct
7 Correct 437 ms 40952 KB Output is correct
8 Correct 133 ms 24348 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15488 KB Output is correct
2 Correct 24 ms 15872 KB Output is correct
3 Correct 25 ms 15872 KB Output is correct
4 Correct 25 ms 15872 KB Output is correct
5 Correct 24 ms 15872 KB Output is correct
6 Correct 27 ms 16036 KB Output is correct
7 Correct 13 ms 15488 KB Output is correct
8 Correct 24 ms 16000 KB Output is correct
9 Correct 14 ms 15744 KB Output is correct
10 Correct 24 ms 15872 KB Output is correct
11 Correct 13 ms 15744 KB Output is correct
12 Correct 15 ms 15872 KB Output is correct
13 Correct 26 ms 16036 KB Output is correct
14 Correct 26 ms 16036 KB Output is correct
15 Correct 26 ms 16036 KB Output is correct
16 Correct 28 ms 16036 KB Output is correct
17 Correct 22 ms 15872 KB Output is correct
18 Correct 16 ms 15744 KB Output is correct
19 Correct 26 ms 16036 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 15744 KB Output is correct
2 Correct 304 ms 40440 KB Output is correct
3 Correct 303 ms 40440 KB Output is correct
4 Correct 266 ms 35448 KB Output is correct
5 Correct 300 ms 35704 KB Output is correct
6 Correct 14 ms 17920 KB Output is correct
7 Correct 437 ms 40952 KB Output is correct
8 Correct 133 ms 24348 KB Output is correct
9 Correct 13 ms 15488 KB Output is correct
10 Correct 24 ms 15872 KB Output is correct
11 Correct 25 ms 15872 KB Output is correct
12 Correct 25 ms 15872 KB Output is correct
13 Correct 24 ms 15872 KB Output is correct
14 Correct 27 ms 16036 KB Output is correct
15 Correct 13 ms 15488 KB Output is correct
16 Correct 24 ms 16000 KB Output is correct
17 Correct 14 ms 15744 KB Output is correct
18 Correct 24 ms 15872 KB Output is correct
19 Correct 13 ms 15744 KB Output is correct
20 Correct 15 ms 15872 KB Output is correct
21 Correct 26 ms 16036 KB Output is correct
22 Correct 26 ms 16036 KB Output is correct
23 Correct 26 ms 16036 KB Output is correct
24 Correct 28 ms 16036 KB Output is correct
25 Correct 22 ms 15872 KB Output is correct
26 Correct 16 ms 15744 KB Output is correct
27 Correct 26 ms 16036 KB Output is correct
28 Correct 577 ms 72604 KB Output is correct
29 Correct 597 ms 68508 KB Output is correct
30 Correct 434 ms 42140 KB Output is correct
31 Correct 533 ms 46236 KB Output is correct
32 Correct 527 ms 45524 KB Output is correct
33 Correct 286 ms 36728 KB Output is correct
34 Correct 610 ms 85128 KB Output is correct
35 Correct 424 ms 65416 KB Output is correct
36 Correct 547 ms 42744 KB Output is correct
37 Correct 572 ms 64096 KB Output is correct
38 Correct 533 ms 84216 KB Output is correct
39 Correct 393 ms 43036 KB Output is correct
40 Correct 482 ms 43164 KB Output is correct
41 Correct 271 ms 36984 KB Output is correct
42 Correct 457 ms 53788 KB Output is correct
43 Correct 508 ms 42396 KB Output is correct
44 Correct 133 ms 25884 KB Output is correct