Submission #656484

#	Time	Username	Problem	Language	Result	Execution time	Memory
656484		ParsaS	T-Covering (eJOI19_covering)	C++17	25 / 100	72 ms	20716 KiB

covering

// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 1e6 + 5, MOD = 1e9 + 7;
const int di[4] = {0, 0, 1, -1}, dj[4] = {1, -1, 0, 0};
const int dx[2] = {1, -1}, dy[2] = {1, 1};
int n, m, cnt, sum, mn;
pair<int, int> P[N];
set<pair<int, int> > st;
vector<vector<int> > grid, vis, mark, G;

bool valid(int i, int j) {
    return min(i, j) >= 0 && i < n && j < m;
}

bool dfs(int i, int j) {
    bool ok = true;
    if (mark[i][j] == 2) {
        for (int k = 0; k < 4; k++) {
            int x = i + di[k], y = j + dj[k];
            if (valid(x, y) && !vis[x][y] && mark[x][y] == 1) {
                ok &= dfs(x, y);
            }
        }
        return ok;

    }
    G[i][j] = true;
    for (int t = 0; t < 4; t++) {
        int x = i + di[t], y = j + dj[t];
        ok &= valid(x, y) && !mark[x][y];
    }
    if (ok) {
        return true;
    }
    vis[i][j] = true;
    bool res = true;
    for (int t = 0; t < 4; t++) {
        int x = i + di[t], y = j + dj[t];

        if ((!valid(x, y) || mark[x][y]) && ok) {
            return false;
        }
        if (!valid(x, y))
            ok = true;
        else {
            if (mark[x][y] == 1) {
                ok = true;
            }
            else
                mark[x][y] = 2;
            if (!vis[x][y])
                res &= dfs(x, y);
        }
    }
    return res;
}
void dfs2(int i, int j) {
    cnt++;
    G[i][j] = true;
    for (int t = 0; t < 4; t++) {
        if (valid(i + di[t], j + dj[t]) && !mark[i + di[t]][j + dj[t]]) {
            st.insert(mp(i + di[t], j + dj[t]));
            sum += grid[i + di[t]][j + dj[t]];
            mn = min(mn, grid[i + di[t]][j + dj[t]]);
        }
        int x = i + 2 * di[t], y = j + 2 * dj[t];
        if (valid(x, y) && mark[x][y] == 1 && !G[x][y]) {
            dfs2(x, y);
        }
    }
}

void solve() {
    cin >> n >> m;
    vector<vector<int> > tmp(n + 3, vector<int>(m + 3));
    vis = tmp;
    mark = G = tmp;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> tmp[i][j];
        }
    }
    grid = tmp;
    int k; cin >> k;

    for (int i = 0; i < k; i++) {
        cin >> P[i].fi >> P[i].se;
        mark[P[i].fi][P[i].se] = 1;
    }
    bool ok = true;
    for (int i = 0; i < k; i++) {
        if (!vis[P[i].fi][P[i].se]) {
            for (int t = 0; t < 4; t++) {
                int x = P[i].fi + di[t], y = P[i].se + dj[t];
                if (!vis[P[i].fi][P[i].se] && (!valid(x, y) || (valid(x, y) && mark[x][y])))
                    ok &= dfs(P[i].fi, P[i].se);
            }
        }
    }
    for (int i = 0; i < k; i++) {
        
        for (int t = 0; t < 2; t++) {
            set<pair<int, int> > S;
            int x = P[i].fi + dx[t], y = P[i].se + dy[t];
            if (valid(x, y) && mark[x][y] == 1) {
                G[x][y] = true;
                G[P[i].fi][P[i].se] = true;
                vis[x][y] = vis[P[i].fi][P[i].se] = true;
                for (int f = 0; f < 4; f++) {
                    S.insert(mp(x + di[f], y + dj[f]));
                    S.insert(mp(P[i].fi + di[f], P[i].se + dj[f]));
                }
                for (auto [a, b] : S) {
                    ok &= valid(a, b) && !mark[a][b];
                    if (!ok)
                        break;
                    mark[a][b] = 2;
                }
                for (auto [a, b] : S) {
                    if (ok)
                        ok &= dfs(a, b);
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < k; i++) {
        int x = P[i].fi, y = P[i].se;
        if (G[x][y] == false) {
            sum = cnt = 0, mn = 1e9 + 5;
            st.clear();
            dfs2(x, y);
            ans += sum;
            if (st.size() < cnt) {
                ok = false;
            }
            else if (st.size() == 3 * cnt + 1) {
                ans -= mn;
            }
        }
    }
    if (!ok) {
        cout << "No" << '\n';
        return;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mark[i][j])
                ans += grid[i][j];
        }
    }
    cout << ans;

}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int tc = 1; //cin >> tc;
    while (tc--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

covering.cpp: In function 'void solve()':
covering.cpp:140:27: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  140 |             if (st.size() < cnt) {
      |                 ~~~~~~~~~~^~~~~
covering.cpp:143:32: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  143 |             else if (st.size() == 3 * cnt + 1) {
      |                      ~~~~~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 30