Submission #330146

#TimeUsernameProblemLanguageResultExecution timeMemory
330146Kevin_Zhang_TWDango Maker (JOI18_dango_maker)C++17
13 / 100
1 ms512 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define pb emplace_back #define AI(i) begin(i), end(i) template<class T> bool chmax(T &a, T b) { return a < b ? (a = b, true) : false; } template<class T> bool chmin(T &a, T b) { return b < a ? (a = b, true) : false; } #ifdef KEV #define DE(args...) kout("[ " + string(#args) + " ] = ", args) void kout() { cerr << endl; } template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); } template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; } #else #define DE(...) 0 #define debug(...) 0 #endif const int MAX_N = 3005, MAX_M = 9000005; char w[MAX_N][MAX_N]; int n, m; int ma[MAX_M], a, b; int id[MAX_N][MAX_N]; bool valid (char a, char b, char c) { return a == 'R' && b == 'G' && c == 'W'; } struct dsu { vector<int> g, sz; dsu(int n) { g.resize(n), sz.resize(n, 1); iota(AI(g), 0); } int F(int i) { return i == g[i] ? i : g[i] = F(g[i]); } bool merge(int a, int b) { a = F(a), b = F(b); if (a == b) return false; if (sz[a] < sz[b]) swap(a, b); return sz[a] += sz[b], g[b] = a, true; } int operator()(int i) { return F(i) ; } }; int solve() { for (int i = 1;i <= n;++i) for (int j = 1;j <= m;++j) { if (valid(w[i][j-1], w[i][j], w[i][j+1])) id[i][j] = ++b; } vector<pair<int,int>> alle; for (int i = 1;i <= n;++i) for (int j = 1;j <= m;++j) { if (valid(w[i-1][j], w[i][j], w[i+1][j])) { ++a; if (id[i-1][j+1]) alle.pb(a, id[i-1][j+1]); if (id[i][j]) alle.pb(a, id[i][j]); if (id[i+1][j-1]) alle.pb(a, id[i+1][j-1]); } } for (auto &[x, y] : alle) y += a; b += a; dsu D(b * 2 + 10); for (auto [x, y] : alle) D.merge(x, y + b), D.merge(x + b, y); int res = 0; vector<int> cnt(b * 2 + 10); for (int i = 1;i <= b;++i) ++cnt[ D(i) ]; for (int i = 1;i <= b;++i) { res += max(cnt[D(i)], cnt[D(i+b)]); cnt[D(i)] = 0, cnt[D(i+b)] = 0; } return res; } int32_t main() { ios_base::sync_with_stdio(0), cin.tie(0); cin >> n >> m; for (int i = 1;i <= n;++i) cin >> w[i] + 1; cout << solve() << '\n'; }

Compilation message (stderr)

dango_maker.cpp: In function 'int32_t main()':
dango_maker.cpp:84:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |   cin >> w[i] + 1;
      |          ~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...