Submission #1288136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288136		Kerim	Game (eJOI20_game)	C++20	100 / 100	6 ms	1348 KiB

game

#include "bits/stdc++.h"

using namespace std;
const int N = 25;
char h[N][N], v[N][N];
int cntv, cnte, vis[N*N];
vector<int> path, cycle;
vector<int> adj[N*N];
void add_edge(int u, int v){
    adj[u].push_back(v);
    // cout<<u<<" "<<v<<endl;
}
void dfs(int nd){
    vis[nd] = 1;
    cntv += 1;
    cnte += adj[nd].size();
    for (auto to: adj[nd])
        if (!vis[to])
            dfs(to);
}
map<vector<int>, int> dp;
int rec(int p, int c, int rem, int what){
    if (p == path.size() and c == cycle.size())
        return rem;
    if (dp.find({p, c, rem, what}) != dp.end())
        return dp[{p, c, rem, what}];
    int &ret=dp[{p, c, rem, what}];
    ret = -1e9;
    if (what == 0 and rem >= 4)//lastly marked cycle
        ret = max(ret, rem-4 - rec(p, c, 4, -1));
    if (what == 1 and rem >= 3)//lastly marked path
        ret = max(ret, rem-2 - rec(p, c, 2, -1));
    if (p < path.size())
        ret = max(ret, rem - rec(p+1, c, path[p], 1));
    if (c < cycle.size())
        ret = max(ret, rem - rec(p, c+1, cycle[c], 0));
    return ret;
}
int main(){
    // freopen("file.in", "r", stdin);
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n+1; i++)
        scanf("%s", h[i]);
    for (int i = 0; i < n; i++)
        scanf("%s", v[i]);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++){
            int u = i*m+j;
            if (i and h[i][j] == '0')
                add_edge(u, u-m);
            if (i + 1 < n and h[i+1][j] == '0')
                add_edge(u, u+m);
            if (j and v[i][j] == '0')
                add_edge(u, u-1);
            if (j + 1 < m and v[i][j+1] == '0')
                add_edge(u, u+1);
            if (h[i][j] == '1' and h[i+1][j] == '1' and 
                v[i][j] == '1' and v[i][j+1] == '1')
                vis[u] = 1;
        }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++){
            int u = i*m+j;
            if (vis[u])
                continue;
            cntv = cnte = 0;
            dfs(u);
            if (cntv * 2 > cnte)
                path.push_back(cntv);
            else
                cycle.push_back(cntv);
        }
    sort(path.begin(), path.end());
    sort(cycle.begin(), cycle.end());
    // for (auto p: path)
    //     printf("%d ", p);
    // puts("");
    // for (auto c: cycle)
    //     printf("%d ", c);
    // puts("");
    printf("%d\n", rec(0, 0, 0, -1));
}

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
game.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%s", h[i]);
      |         ~~~~~^~~~~~~~~~~~
game.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         scanf("%s", v[i]);
      |         ~~~~~^~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20