제출 #755724

#제출 시각아이디문제언어결과실행 시간메모리
755724KihihihiDango Maker (JOI18_dango_maker)C++17
13 / 100
136 ms262144 KiB
#include <iostream> #include <iomanip> #include <algorithm> #include <numeric> #include <cmath> #include <cassert> #include <ctime> #include <chrono> #include <cstdio> #include <random> #include <vector> #include <string> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <deque> #include <queue> #include <bitset> #include <list> #include <fstream> #include <functional> #include <complex> using namespace std; mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count()); const long long INF = 1e18, MOD = 1e9 + 7, MOD2 = 998244353, LOG = 18; const long double EPS = 1e-9, PI = acos(-1); void solve() { long long n, m; vector<string> t; cin >> n >> m; t.resize(n); for (long long i = 0; i < n; i++) { cin >> t[i]; } function<bool(long long, long long)> check_vert = [&](long long x, long long y) { if (x < 0 || x >= n - 2) { return false; } return t[x][y] == 'R' && t[x + 1][y] == 'G' && t[x + 2][y] == 'W'; }; vector<vector<long long>> ver_idx(n, vector<long long>(m, -1)); long long rsz = 0; for (long long i = 0; i < n - 2; i++) { for (long long j = 0; j < m; j++) { if (check_vert(i, j)) { ver_idx[i][j] = rsz++; } } } vector<vector<long long>> g; vector<long long> mt(rsz, -1); for (long long i = 0; i < n; i++) { for (long long j = 0; j < m - 2; j++) { if (t[i][j] != 'R' || t[i][j + 1] != 'G' || t[i][j + 2] != 'W') { continue; } g.push_back({}); if (check_vert(i, j)) { g.back().push_back(ver_idx[i][j]); } if (check_vert(i - 1, j + 1)) { g.back().push_back(ver_idx[i - 1][j + 1]); } if (check_vert(i - 2, j + 2)) { g.back().push_back(ver_idx[i - 2][j + 2]); } } } long long lsz = g.size(); long long tmr = 0; vector<bool> used(lsz, -1); function<bool(long long)> kuhn = [&](long long v) { if (used[v] == tmr) { return false; } used[v] = tmr; for (auto& i : g[v]) { if (mt[i] == -1 || kuhn(i)) { mt[i] = v; return true; } } return false; }; for (long long i = 0; i < lsz; i++) { kuhn(i); tmr++; } vector<bool> in_mt(lsz); for (long long i = 0; i < rsz; i++) { if (mt[i] == -1) { continue; } in_mt[mt[i]] = true; } vector<bool> visl(lsz), visr(rsz); function<void(long long)> dfs = [&](long long v) { visl[v] = true; for (auto& i : g[v]) { if (mt[i] == v || visr[i]) { continue; } visr[i] = true; if (mt[i] != -1 && !visl[mt[i]]) { dfs(mt[i]); } } }; for (long long i = 0; i < lsz; i++) { if (in_mt[i] || visl[i]) { continue; } dfs(i); } long long ans = count(visl.begin(), visl.end(), true) + count(visr.begin(), visr.end(), false); cout << ans << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); srand(time(NULL)); int tst = 1; //cin >> tst; while (tst--) { solve(); } return 0; } /* <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 ⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠤⠖⠚⢉⣩⣭⡭⠛⠓⠲⠦⣄⡀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⢀⡴⠋⠁⠀⠀⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠳⢦⡀⠀⠀⠀⠀ ⠀⠀⠀⠀⢀⡴⠃⢀⡴⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣆⠀⠀⠀ ⠀⠀⠀⠀⡾⠁⣠⠋⠀⠈⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⠀⠀ ⠀⠀⠀⣸⠁⢰⠃⠀⠀⠀⠈⢣⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣇⠀ ⠀⠀⠀⡇⠀⡾⡀⠀⠀⠀⠀⣀⣹⣆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀ ⠀⠀⢸⠃⢀⣇⡈⠀⠀⠀⠀⠀⠀⢀⡑⢄⡀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇ ⠀⠀⢸⠀⢻⡟⡻⢶⡆⠀⠀⠀⠀⡼⠟⡳⢿⣦⡑⢄⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇ ⠀⠀⣸⠀⢸⠃⡇⢀⠇⠀⠀⠀⠀⠀⡼⠀⠀⠈⣿⡗⠂⠀⠀⠀⠀⠀⠀⠀⢸⠁ ⠀⠀⡏⠀⣼⠀⢳⠊⠀⠀⠀⠀⠀⠀⠱⣀⣀⠔⣸⠁⠀⠀⠀⠀⠀⠀⠀⢠⡟⠀ ⠀⠀⡇⢀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⢸⠃⠀ ⠀⢸⠃⠘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠁⠀⠀⢀⠀⠀⠀⠀⠀⣾⠀⠀ ⠀⣸⠀⠀⠹⡄⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⡞⠀⠀⠀⠸⠀⠀⠀⠀⠀⡇⠀⠀ ⠀⡏⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⠀⢀⣠⢶⡇⠀⠀⢰⡀⠀⠀⠀⠀⠀⡇⠀⠀ ⢰⠇⡄⠀⠀⠀⡿⢣⣀⣀⣀⡤⠴⡞⠉⠀⢸⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⣧⠀⠀ ⣸⠀⡇⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⢹⠀⠀⢸⠀⠀⢀⣿⠇⠀⠀⠀⠁⠀⢸⠀⠀ ⣿⠀⡇⠀⠀⠀⠀⠀⢀⡤⠤⠶⠶⠾⠤⠄⢸⠀⡀⠸⣿⣀⠀⠀⠀⠀⠀⠈⣇⠀ ⡇⠀⡇⠀⠀⡀⠀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠸⡌⣵⡀⢳⡇⠀⠀⠀⠀⠀⠀⢹⡀ ⡇⠀⠇⠀⠀⡇⡸⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠮⢧⣀⣻⢂⠀⠀⠀⠀⠀⠀⢧ ⣇⠀⢠⠀⠀⢳⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡎⣆⠀⠀⠀⠀⠀⠘ ⢻⠀⠈⠰⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠘⢮⣧⡀⠀⠀⠀⠀ ⠸⡆⠀⠀⠇⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠆⠀⠀⠀⠀⠀⠀⠀⠙⠳⣄⡀⢢⡀ <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...