제출 #800511

#제출 시각아이디문제언어결과실행 시간메모리
800511thimote75바이러스 (JOI19_virus)C++14
0 / 100
325 ms262144 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 (unordered_set<int> &interieur, 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 = interieur.find(S) != interieur.end(); bool hN = interieur.find(N) != interieur.end(); bool hW = interieur.find(W) != interieur.end(); bool hE = interieur.find(E) != interieur.end(); 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 MFC { unordered_set<int> frontiere; unordered_set<int> routes; unordered_set<int> interieur; unordered_set<int> rem_routes; MFC () = default; int getRoute () { while (routes.size() != 0) { int route = (*routes.begin()); routes.erase(route); if (interieur.find(route) != interieur.end()) continue ; rem_routes.insert(route); return route; } return -1; } int roadCount () { int res = 0; for (int u : routes) if (interieur.find(u) == interieur.end()) res ++; for (int u : rem_routes) if (interieur.find(u) == interieur.end()) res ++; return res; } void merge (MFC* other) { if (other->frontiere.size() > frontiere.size()) other->frontiere.swap(frontiere); if (other->interieur.size() > interieur.size()) other->interieur.swap(interieur); if (other->routes.size() > routes.size()) other->routes.swap(routes); if (other->rem_routes.size() > rem_routes.size()) other->rem_routes.swap(rem_routes); for (int u : other->interieur) interieur.insert(u); for (int u : other->routes) routes.insert(u); for (int u : other->rem_routes) rem_routes.insert(u); for (int u : other->frontiere) { if (check_road(interieur, u)) { if (frontiere.find(u) != frontiere.end()) frontiere.erase(u); routes.insert(u); } else frontiere.insert(u); } } }; struct UFD { vector<MFC*> metadatas; idata parents; UFD () = default; UFD (int size) { metadatas.resize(size); 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); parents[b] = a; metadatas[a]->merge(metadatas[b]); } }; UFD ufd; 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; } bdata visited, visiting; idata depth; int dfs (int node, int parent, int _depth) { if (visiting[node]) { return _depth - depth[node] - 1; } if (visited[node]) return 0; visited [node] = true; visiting[node] = true; depth [node] = _depth; MFC* mfc = ufd.metadatas[ufd.boss(node)]; while (true) { int data = mfc->getRoute(); if (data == -1) break ; data = ufd.boss(data); int res = dfs(data, node, _depth + 1); if (res == 0) continue ; ufd.merge(parent, node); return res - 1; } return 0; } 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); for (int i = 0; i < R * C; i ++) { MFC* mfc = new MFC(); ufd.metadatas[i] = mfc; if (U[i] == 0) continue ; mfc->interieur.insert(i); vector<int> adjacent; if (i >= C) adjacent.push_back(i - C); if (i < R * C - C) adjacent.push_back(i + C); if (i % C != 0) adjacent.push_back(i - 1); if (i % C != C - 1) adjacent.push_back(i + 1); unordered_set<int> G; G.insert(i); for (int adj : adjacent) { if (check_road(G, adj)) mfc->routes.insert(adj); else mfc->frontiere.insert(adj); } } visited.resize(R * C); visiting.resize(R * C); depth.resize(R * C); for (int i = 0; i < R * C; i ++) { if (visited[i]) continue ; dfs(i, -1, 0); } int res = 1e9; int cnt = 0; for (int u = 0; u < R * C; u ++) { int v = ufd.boss(u); if (u != v) continue ; int rsize = ufd.metadatas[v]->roadCount(); if (rsize != 0) continue ; int size = ufd.metadatas[v]->interieur.size(); if (size == 0) continue ; if (size > res) continue ; if (size != res) cnt = 0; cnt += size; res = size; } cout << res << endl << cnt << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...