Submission #1105979

#TimeUsernameProblemLanguageResultExecution timeMemory
1105979SoulKnightDango Maker (JOI18_dango_maker)C++17
Compilation error
0 ms0 KiB
#include "bits/stdc++.h" using namespace std; #define ln '\n' const int N = 3e3 + 5; const string S = "RGW"; struct hhh{ int horiz = -1, vert = -1; } a[N][N]; int n, m, glit = 1; string grid[N]; vector<int> adj[N*N/3]; bool vis[N*N/3]; int dp[N*N/3][2]; void dfs(int u, int p){ int take = 0, no_take = 0; vis[u] = 1; for (auto v: adj[u]){ if (v == p) continue; dfs(v, u); take += dp[v][1]; no_take += dp[v][0]; } dp[u][0] = take; dp[u][1] = 1 + no_take; } void solve(){ cin >> n >> m; for (int i = 0; i < n; i++) cin >> grid[i]; for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ bool ok = true; for (int k = 0; k <= 2; k++){ int ti = i, tj = j + k; if (ti < 0 || ti > n-1 || tj < 0 || tj > m-1) {ok = false; break;} if (grid[ti][tj] != S[k]) {ok = false; break;} } if (ok) a[i][j+1].horiz = glit++; ok = true; for (int k = 0; k <= 2; k++){ int ti = i+k, tj = j; if (ti < 0 || ti > n-1 || tj < 0 || tj > m-1) {ok = false; break;} if (grid[ti][tj] != S[k]) {ok = false; break;} } if (ok) a[i+1][j].vert = glit++; } } for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ int u = a[i][j].horiz, v = a[i][j].vert; if (u != -1 && v != -1) adj[u].push_back(v), adj[v].push_back(u); if (i+1 >= n || j-1 < 0) continue; u = a[i][j].horiz, v = a[i+1][j-1].vert; if (u != -1 && v != -1) adj[u].push_back(v), adj[v].push_back(u); // cout << u << ' ' << v << ln; } } // maximum independent set in this forest int ans = 0; for (int i = 1; i < glit; i++){ if (vis[i]) continue; dfs(i, -1); ans += max(dp[i][0], dp[i][1]); } cout << ans << ln; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }

Compilation message (stderr)

Compilation timeout while compiling dango_maker