제출 #230791

#제출 시각아이디문제언어결과실행 시간메모리
230791walnutwaldo20바이러스 (JOI19_virus)C++14
6 / 100
27 ms2268 KiB
#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 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); assert(memcounter < 2e8); } } } 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, 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); memcounter += sizeof(p); assert(memcounter < 2e8); } } 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>()); memcounter += sizeof(comps.top()); memcounter += sizeof(adjs.top()); assert(memcounter < 2e8); 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); memcounter += sizeof(next); assert(memcounter < 2e8); } } } } 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); 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); cin >> m >> r >> c; assert(r * c < 100000); 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; assert(memcounter < 2e8); //cout << memcounter << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...