제출 #800595

#제출 시각아이디문제언어결과실행 시간메모리
800595thimote75바이러스 (JOI19_virus)C++14
0 / 100
2096 ms164528 KiB
#include <bits/stdc++.h> using namespace std; using bdata = vector<bool>; using idata = vector<int>; using igrid = vector<idata>; using ispac = vector<igrid>; string to_string(string s) { return s; } template <typename T> string to_string(T v) { bool first = true; string res = "["; for (const auto &x : v) { if (!first) res += ", "; first = false; res += to_string(x); } res += "]"; return res; } template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } void dbg_out() { cout << endl; } template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << to_string(H); dbg_out(T...); } #ifdef DEBUG #define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #else #define dbg(...) #endif int R, C; const int MASK_S = 1; const int MASK_N = 2; const int MASK_W = 4; const int MASK_E = 8; idata U; int max_buffer[16]; bool check_road (idata &visited, int stage, int u) { if (U[u] == 0) return false; int S = u + C; int N = u - C; int W = u % C == 0 ? - 1 : u - 1; int E = u % C == C - 1 ? - 1 : u + 1; bool hS = S >= 0 && S < R * C ? visited[S] == stage : false; bool hN = N >= 0 && N < R * C ? visited[N] == stage : false; bool hW = W >= 0 && W < R * C ? visited[W] == stage : false; bool hE = E >= 0 && E < R * C ? visited[E] == stage : false; for (int m = 1; m < 16; m ++) { if (U [u] > max_buffer[m]) continue ; if ((m & MASK_S) != 0 && (!hS)) continue ; if ((m & MASK_N) != 0 && (!hN)) continue ; if ((m & MASK_W) != 0 && (!hW)) continue ; if ((m & MASK_E) != 0 && (!hE)) continue ; return true; } return false; } struct Mare { set<int> cases; int center; bool is_in (int x) { return cases.find(x) != cases.end(); } void merge (Mare &other) { if (cases.size() < other.cases.size()) cases.swap(other.cases); for (int u : other.cases) cases.insert(u); } bool operator< (const Mare right) const { if (cases.size() == right.cases.size()) return center < right.center; return cases.size() < right.cases.size(); } bool operator== (const Mare right) const { return center == right.center; } }; struct Comp { bool operator() (const Mare* A, const Mare* B) const { return (*A) < (*B); } }; using vMare = vector<Mare>; using sMare = set<Mare>; struct UFD { vMare mares; sMare sorted_mares; idata parents; int rem () { return sorted_mares.size(); } Mare pop () { Mare mare = *sorted_mares.begin(); sorted_mares.erase(mare); return mare; } UFD () = default; UFD (int size) { mares.resize(size); for (int i = 0; i < size; i ++) { mares[i].cases.insert(i); mares[i].center = i; sorted_mares.insert(mares[i]); } parents.resize(size); iota(parents.begin(), parents.end(), 0); } int boss (int x) { if (parents[x] != x) parents[x] = boss(parents[x]); return parents[x]; } void merge (int a, int b) { a = boss(a); b = boss(b); if (a == b) return ; parents[b] = a; sorted_mares.erase(mares[a]); sorted_mares.erase(mares[b]); mares[a].merge(mares[b]); sorted_mares.insert(mares[a]); } }; int solve_buffer (bdata &values) { int r = 0; int l = 0; int c = 0; for (bool u : values) { if (u) { if (l == 0) { l = 1; c = 0; } c ++; r = max(r, c); } else l = 0; } for (bool u : values) { if (u) { if (l == 0) { l = 1; c = 0; } c ++; r = max(r, c); } else l = 0; } return r; } UFD ufd; idata visited; int stage = 0; pair<int, int> find_outside (Mare mare) { if (U[mare.center] == 0) return { -1, 1e9 }; int start = mare.center; stage ++; queue<int> q; visited[start] = stage; q.push(start); int cnt = 0; while (q.size() != 0) { int curr = q.front(); q.pop(); //dbg(curr); cnt ++; for (int adjacent : { curr - C, curr + C, curr % C == 0 ? - 1 : curr - 1, curr % C == C + 1 ? - 1 : curr + 1 }) { if (adjacent < 0 || adjacent >= R * C) continue ; //dbg(adjacent); //dbg(visited[adjacent]); //dbg(stage); //dbg((int) (visited[adjacent] == stage)); if (visited[adjacent] == stage) continue ; //dbg((int) (check_road(visited, stage, adjacent))); if (!check_road(visited, stage, adjacent)) continue ; //dbg((int) (mare.is_in(adjacent))); if (!mare.is_in(adjacent)) return { adjacent, cnt }; q.push(adjacent); visited[adjacent] = stage; } } return { -1, cnt }; } int main () { ios_base::sync_with_stdio(false); cin.tie(NULL); int T; cin >> T; cin >> R >> C; string buffer; cin >> buffer; bdata values(T); for (int m = 1; m < 16; m ++) { for (int i = 0; i < T; i ++) { values[i] = false; if (buffer[i] == 'S' && (0 != (m & MASK_S))) values[i] = true; if (buffer[i] == 'N' && (0 != (m & MASK_N))) values[i] = true; if (buffer[i] == 'W' && (0 != (m & MASK_W))) values[i] = true; if (buffer[i] == 'E' && (0 != (m & MASK_E))) values[i] = true; } max_buffer[m] = solve_buffer(values); } U.resize(R * C); for (int r = 0; r < R; r ++) { for (int c = 0; c < C; c ++) { cin >> U[r * C + c]; } } ufd = UFD(R * C); visited.resize(R * C); while (ufd.rem() != 0) { Mare mare = ufd.pop(); int out = find_outside(mare).first; if (out == -1) continue ; ufd.sorted_mares.insert(ufd.mares[mare.center]); ufd.merge(out, mare.center); } int res = 1e9; int cnt = 0; for (int u = 0; u < R * C; u ++) { if (ufd.boss(u) != u) continue ; int size = find_outside(ufd.mares[u]).second; if (size > res) continue ; if (size < res) cnt = 0; res = size; cnt += size; } cout << res << "\n" << cnt << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...