제출 #230746

#제출 시각아이디문제언어결과실행 시간메모리
230746walnutwaldo20바이러스 (JOI19_virus)C++14
0 / 100
2081 ms54092 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; bool vis[MAXN], 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; 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; } } } void tarjan(pii loc) { vis[codefor(loc)] = true; on[codefor(loc)] = true; 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 (root(codefor(next)) == root(codefor(loc))) { continue; } if (vis[codefor(next)]) { if (on[codefor(next)]) { pii curr = loc; while (curr != next) { pii nextup = dfspar[codefor(curr)]; join(codefor(curr), codefor(nextup), tosearch); curr = nextup; } } else { continue; } } else { dfspar[codefor(next)] = loc; tarjan(next); } } on[codefor(loc)] = false; } 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...