제출 #800654

#제출 시각아이디문제언어결과실행 시간메모리
800654rnl42바이러스 (JOI19_virus)C++14
6 / 100
2080 ms18636 KiB
#include <bits/stdc++.h> using namespace std; #define amax(a, b) a = max(a, b) #define cellid(r, c) (r*C+c) #define extract(cell) (cell/C)][(cell%C) 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 constexpr int INF = 1e9+42; int M, R, C; vector<vector<int>> U; string to_s(int cell) { return to_string(cell/C)+","+to_string(cell%C); } struct patate { int centre; int num_cases = 1; bool operator<(const patate& other) const { return num_cases > other.num_cases; } }; struct Dir { int v, h; bool ok(int cell) { int r = cell/C, c = cell%C; if (0 <= r+v && r+v < R && 0 <= c+h && c+h < C && U[r+v][c+h]) { return true; } else { return false; } } int next(int cell) { return cell+h+v*C; } }; const Dir DIRS[] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; int maxconsecutive[1<<4]; //vector<patate> patates; vector<int> uf; vector<int> numchilds; priority_queue<patate> pq; int timer = 1; vector<int> vu; int ans = INF; int ansq = 0; //vector<int> maskvoisin; int root(int u) { return uf[u] == u ? u : uf[u] = root(uf[u]); } void debug_plateau() { for (int r = 0; r < R; r++) { for (int c = 0; c < C; c++) { if (U[r][c]) { auto color = root(cellid(r, c)); color %= 14; if (color >= 7) color += 4; //cerr << "\033[" << color+31 << "m" << root(cellid(r, c)) << "\033[0m "; } else { //cerr << "\033[90m" << root(cellid(r, c)) << "\033[0m "; } } //cerr << "\n"; } } int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> M >> R >> C; string dirs; cin >> dirs; dirs.append(dirs); char _map[256]; _map['S'] = 0; _map['W'] = 1; _map['N'] = 2; _map['E'] = 3; uf.resize(R*C); vu.resize(R*C); numchilds.assign(R*C, 1); //maskvoisin.resize(R*C); iota(uf.begin(), uf.end(), 0); for (int mask = 0; mask < 1<<4; mask++) { int l = 0; for (char c : dirs) { if ((mask >> _map[(unsigned char)c]) & 1) l++; else l = 0; maxconsecutive[mask] = max(maxconsecutive[mask], l); } if (maxconsecutive[mask] >= M) maxconsecutive[mask] = INF; //cerr << "maxconsecutive[" << mask << "] = " << maxconsecutive[mask] << endl; } U.assign(R, vector<int>(C)); for (int r = 0; r < R; r++) { for (int c = 0; c < C; c++) { cin >> U[r][c]; if (U[r][c]) { pq.push({cellid(r, c), 1}); } } } for (int r = 0; r < R; r++) { for (int c = 0; c < C; c++) { int cell = cellid(r, c); if (!U[r][c]) continue; queue<int> q; q.push(cell); timer++; vu[cell] = timer; int num_explore = 0; while (!q.empty()) { auto u = q.front(); q.pop(); num_explore++; for (auto dir : DIRS) { int next = dir.next(u); if (dir.ok(u)) { int i = 2; int mask = 0; for (auto dir2 : DIRS) { int k = dir2.next(next); if (dir2.ok(next) && vu[k] == vu[cell]) { mask += 1<<i; } i++, i &= 3; } if (U[extract(next)] <= maxconsecutive[mask]) { if (vu[next] != timer) { vu[next] = timer; q.push(next); } } } } } if (num_explore == ans) { ansq++; } else if (num_explore < ans) { ans = num_explore; ansq = 1; } } } cout << ans << '\n' << ansq << '\n'; return 0; debug_plateau(); while (!pq.empty()) { auto cur = pq.top(); pq.pop(); if (root(cur.centre) != cur.centre || numchilds[cur.centre] != cur.num_cases) continue; //cerr << "\033[1m\033[93mBFS DEPUIS " << to_s(cur.centre) << "\033[0m" << endl; timer++; queue<int> q; q.push(cur.centre); vu[cur.centre] = timer; bool stopbfs = false; int num_explore = 0; while (!q.empty() && !stopbfs) { auto u = q.front(); q.pop(); num_explore++; for (auto dir : DIRS) { int next = dir.next(u); //cerr << "dir" << dir.v << ":" << dir.h << " u=" << u << endl; if (dir.ok(u)) { int i = 2; int mask = 0; for (auto dir2 : DIRS) { int k = dir2.next(next); if (dir2.ok(next) && vu[k] == vu[cur.centre]) { mask += 1<<i; } i++, i &= 3; } //cerr << "vers dir" << dir.v << ":" << dir.h << " mask=" << mask << endl; if (U[extract(next)] <= maxconsecutive[mask]) { //cerr << "arête valide vers dir" << dir.v << ":" << dir.h << endl; // arête valide if (vu[next] != timer && root(next) == cur.centre) { vu[next] = timer; q.push(next); //cerr << "ajout à la file de " << next << " a pour root" << root(next) << endl; } else if (root(next) != cur.centre) { //cerr << "FUSION " << to_s(root(cur.centre)) << " " << to_s(root(next)) << endl; uf[cur.centre] = root(next); numchilds[root(next)] += numchilds[cur.centre]; //cerr << "push " << to_s(root(next)) << " " << numchilds[root(cur.centre)] << endl; pq.push({root(next), numchilds[root(cur.centre)]}); stopbfs = true; break; } } } } } debug_plateau(); if (!stopbfs) { if (num_explore == ans) { ansq += num_explore; } else if (num_explore < ans) { ans = num_explore; ansq = num_explore; } //cerr << "\033[1m\033[92mmise à jour du min " << num_explore << "\033[0m" << endl; } //cerr << "--------------\n\n\n" << endl; } //... cout << ans << '\n' << ansq << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...