제출 #756079

#제출 시각아이디문제언어결과실행 시간메모리
756079KihihihiDango Maker (JOI18_dango_maker)C++17
33 / 100
1 ms468 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 int INF = 1e9, MOD = 1e9 + 7, MOD2 = 998244353, LOG = 18; const long double EPS = 1e-9, PI = acos(-1); bool check_vert(vector<string>& t, int x, int y) { if (x < 0 || x >= t.size() - 2) { return false; } return t[x][y] == 'R' && t[x + 1][y] == 'G' && t[x + 2][y] == 'W'; } bool kuhn(vector<vector<int>>& g, int v, vector<int>& mt, vector<int>& used, int tmr) { if (used[v] == tmr) { return false; } used[v] = tmr; for (auto& i : g[v]) { if (mt[i] == -1 || kuhn(g, mt[i], mt, used, tmr)) { mt[i] = v; return true; } } return false; }; void dfs(vector<vector<int>>& g, int v, vector<bool>& visl, vector<bool>& visr, vector<int>& mt) { 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(g, mt[i], visl, visr, mt); } } }; void solve() { int n, m; vector<string> t; cin >> n >> m; t.resize(n); for (int i = 0; i < n; i++) { cin >> t[i]; } vector<vector<int>> ver_idx(n, vector<int>(m, -1)); int rsz = 0; for (int i = 0; i < n - 2; i++) { for (int j = 0; j < m; j++) { if (check_vert(t, i, j)) { ver_idx[i][j] = rsz++; } } } vector<vector<int>> g; vector<int> mt(rsz, -1); for (int i = 0; i < n; i++) { for (int 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(t, i, j)) { g.back().push_back(ver_idx[i][j]); } if (check_vert(t, i - 1, j + 1)) { g.back().push_back(ver_idx[i - 1][j + 1]); } if (check_vert(t, i - 2, j + 2)) { g.back().push_back(ver_idx[i - 2][j + 2]); } } } int lsz = g.size(); int tmr = 0; vector<int> used(lsz, -1); for (int i = 0; i < lsz; i++) { kuhn(g, i, mt, used, tmr); tmr++; } vector<bool> in_mt(lsz); for (int i = 0; i < rsz; i++) { if (mt[i] == -1) { continue; } in_mt[mt[i]] = true; } vector<bool> visl(lsz), visr(rsz); for (int i = 0; i < lsz; i++) { if (in_mt[i] || visl[i]) { continue; } dfs(g, i, visl, visr, mt); } int 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 */

컴파일 시 표준 에러 (stderr) 메시지

dango_maker.cpp: In function 'bool check_vert(std::vector<std::__cxx11::basic_string<char> >&, int, int)':
dango_maker.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     if (x < 0 || x >= t.size() - 2)
      |                  ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...