Submission #652175

#TimeUsernameProblemLanguageResultExecution timeMemory
652175KahouT-Covering (eJOI19_covering)C++14
10 / 100
96 ms102400 KiB
/* In the name of God, aka Allah */
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mk make_pair
#define endl '\n'
#define kill(x) if (x) return cout << "No" << endl, void()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int inf = 1e9 + 5;
const int N = 1e6 + 5;
int m, n, k;
vector<int> grid[N];
vector<int> mark[N];
vector<int> seen[N];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int dx2[] = {-1, 1, 1, -1};
int dy2[] = {1, 1, -1, -1};

ll ans;
int t;
int bk[N];
int mn[N];
vector<int> adj[N];
bool vis[N];

bool val(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
}

int f(int x, int y) {
        return x*n + y;
}

void dfs(int u, int p) {
        vis[u] = 1;
        int x = u/n, y = u%n;
        seen[x][y] = 1;
        ans += grid[x][y];
        for (int i = 0; i < 4; i++) {
                if (!val(x+dx[i], y+dy[i])) {
                        ans += -inf;
                        mn[t] = min(mn[t], -inf);
                        continue;
                }
                if (seen[x+dx[i]][y+dy[i]]) continue;
                seen[x+dx[i]][y+dy[i]] = 1;
                ans += grid[x+dx[i]][y+dy[i]];
                mn[t] = min(grid[x+dx[i]][y+dy[i]], mn[t]);
        }
        for (int v:adj[u]) {
                if (v == p) continue;
                if (!vis[v]) dfs(v, u);
                else if (vis[v] == 1) bk[t]++;
        }
        vis[u] = 2;
}


void solve() {
        cin >> m >> n;
        for (int r = 0; r < m; r++) {
                grid[r].resize(n);
                mark[r].resize(n);
                seen[r].resize(n);
                for (int c = 0; c < n; c++) {
                        cin >> grid[r][c];
                }
        }
        cin >> k;
        for (int i = 1; i <= k; i++) {
                int r,c;
                cin >> r >> c;
                mark[r][c] = 1;
        }

        // DOJOB


        for (int x = 0; x < m; x++) {
                for (int y = 0; y < n; y++) {
                        for (int i = 0; i < 4; i++) {
                                if (val(x+2*dx[i], y+2*dy[i]) && mark[x][y] && mark[x+2*dx[i]][y+2*dy[i]]) {
                                        int u = f(x, y);
                                        int v = f(x+2*dx[i], y+2*dy[i]);
                                        adj[u].push_back(v);
                                }
                        }

                }
        }
        for (int x = 0; x < m; x++) {
                for (int y = 0; y < n; y++) {
                        if (mark[x][y]) {
                                int u = f(x,y);
                                if (vis[u]) continue;

                                t++;
                                mn[t] = inf;
                                dfs(u, u);
                                kill(bk[t] >= 2);
                                if (!bk[t]) {
                                        ans -= mn[t];
                                }
                        }
                }
        }
        kill(ans < 0);
        cout << ans << endl;
}

int main() {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        solve();
        return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...