Submission #283996

#	Time	Username	Problem	Language	Result	Execution time	Memory
283996		valerikk	T-Covering (eJOI19_covering)	C++17	100 / 100	298 ms	33784 KiB

covering

#include<bits/stdc++.h>
using namespace std;
 
#define F first
#define S second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define pw(x) (1LL<<x)
#define epr(...) fprintf(stderr, __VA_ARGS__); fflush(stderr)
 
#define db(x) cerr << #x << " = " << x << '\n'
#define db2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n";
#define db3(x, y, z) cerr << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", " << z << ")\n"
#define dbv(a) cerr << #a << " = "; for (auto xxxx: a) cerr << xxxx << " "; cerr << '\n'
 
typedef long long ll;
typedef double dbl;
const int INF = 1e9 + 17;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
 
int solve(int n, int m, vector<vector<int>> a, int k, vector<pair<int, int>> t) {
    auto check = [&](int i, int j) {
        return i >= 0 && i < n && j >= 0 && j < m;
    };
 
    vector<vector<int>> id(n, vector<int>(m, -1));
    for (int i = 0; i < k; ++i) {
        id[t[i].F][t[i].S] = i;
    }
    vector<vector<int>> e(k);
    for (int i = 0; i < k; ++i) {
        for (int x = -2; x <= 2; ++x) {
            for (int y = -2; y <= 2; ++y) {
                pair<int,int> to = {t[i].F + x, t[i].S + y};
                if (check(to.F, to.S) && abs(x) + abs(y) != 0 && abs(x) + abs(y) <= 2 && id[to.F][to.S] != -1) {
                    e[i].pb(id[to.F][to.S]);
                }
            }
        }
    }
 
    vector<bool> used(k, false);
    vector<int> comp;
    function<void(int)> dfs = [&](int v) {
        used[v] = true;
        comp.pb(v);
        for (auto u: e[v]) {
            if (!used[u]) {
                dfs(u);
            }
        }
    };
    int res = 0;
    for (int i = 0; i < k; ++i) {
        res += a[t[i].F][t[i].S];
    }
    vector<vector<bool>> taken(n, vector<bool>(m, false));
    for (int i = 0; i < k; ++i) {
        if (!used[i]) {
            comp = {};
            dfs(i);
 
            vector<pair<int,int>> cur;
            for (auto v: comp) {
                for (int d = 0; d < 4; ++d) {
                    pair<int,int> to = {t[v].F + dx[d], t[v].S + dy[d]};
                    if (check(to.F, to.S) && id[to.F][to.S] == -1 && !taken[to.F][to.S]) {
                        taken[to.F][to.S] = true;
                        cur.pb(to);
                    }
                }
            }
            int need = sz(comp) * 3;
            if (sz(cur) < need) {
                return -INF;
            }
            for (auto it: cur) {
                res += a[it.F][it.S];
            }
            if (sz(cur) > need) {
                int mn = INF;
                for (auto it: cur) {
                    if (a[it.F][it.S] < mn) {
                        mn = a[it.F][it.S];
                    }
                }
                res -= mn;
            }
        }
    }
 
    return res;
}
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            scanf("%d", &a[i][j]);
        }
    }
 
    int k;
    scanf("%d", &k);
    vector<pair<int,int>> t(k);
    for (int i = 0; i < k; ++i) {
        scanf("%d %d", &t[i].F, &t[i].S);
    }
 
    int answer = solve(n, m, a, k, t);
    if (answer == -INF) {
        printf("No\n");
    } else {
        printf("%d\n", answer);
    }
    return 0;
}

Compilation message (stderr)

covering.cpp: In function 'int main()':
covering.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
covering.cpp:102:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |             scanf("%d", &a[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~
covering.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |     scanf("%d", &k);
      |     ~~~~~^~~~~~~~~~
covering.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  110 |         scanf("%d %d", &t[i].F, &t[i].S);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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