Submission #330210

#TimeUsernameProblemLanguageResultExecution timeMemory
330210Kevin_Zhang_TWDango Maker (JOI18_dango_maker)C++17
33 / 100
8 ms11372 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 = MAX_N;//MAX_M = MAX_N * MAX_N / 3 << 1; char w[MAX_N][MAX_N]; int n, m, a, b, id[MAX_N][MAX_N]; bool valid (char a, char b, char c) { return a == 'R' && b == 'G' && c == 'W'; } array<int,3> edge[MAX_M]; int ma[MAX_M], vist[MAX_M], deg[MAX_M], lst[MAX_M]; int Time; void expand(int x, int y) { while (true) { int u = ma[x]; ma[x] = y, ma[y] = x; if (u == -1) return; y = u, x = lst[y]; } } bool dfs(int x) { queue<int> q; q.push(x); vist[x] = Time; lst[x] = 0; while (q.size()) { int x = q.front(); q.pop(); for (int i = 0;i < deg[x];++i) { int u = edge[x][i]; if (ma[u] == -1) return expand(x, u), true; lst[u] = x; if (exchange(vist[u], Time) != Time) q.emplace(ma[u]); } } return false; } int max_clique() { b += a; memset(ma, -1, sizeof(ma)); int res = b; for (int i = 1;i <= a;++i) if (ma[i] == -1 && (Time = i, dfs(i))) --res; return res; } 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] = ++a; } 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])) { ++b; for (int x : {id[i-1][j+1], id[i][j], id[i+1][j-1]}) if (x) { edge[x][ deg[x]++ ] = b + a; } } } return max_clique(); } 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:89:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |   cin >> w[i] + 1;
      |          ~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...