Submission #843833

#	Time	Username	Problem	Language	Result	Execution time	Memory
843833		otarius	T-Covering (eJOI19_covering)	C++17	100 / 100	248 ms	56940 KiB

covering

#pragma GCC optimize("Ofast")
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;
 
#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair <int, int>
#define ull unsigned long long
 
// #define int long long
// #define int unsigned long long
 
const ll inf = 1e9 + 7;
const ll weirdMod = 998244353;

int x, y, ans, cur;
int a[1000050], idx, n, m;
vector<int> adj[1000050], vec;
bool used[1000050], isred[1000050];
void dfs(int v) {
    used[v] = 1;
    if (isred[v]) cur++;
    else vec.pb(a[v]);
    for (int u : adj[v]) {
        if (!used[u]) dfs(u);
    }
}
void solve() {
    cin >> n >> m; idx = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[idx++];
        }
    } int k;
    cin >> k;
    for (int i = 1; i <= k; i++) {
        cin >> x >> y; x++; y++;
        ans += a[(x - 1) * m + y];
        isred[(x - 1) * m + y] = 1;
        if (x > 1) {
            adj[(x - 1) * m + y].pb((x - 2) * m + y);
            adj[(x - 2) * m + y].pb((x - 1) * m + y);
        } if (x < n) {
            adj[(x - 1) * m + y].pb(x * m + y);
            adj[x * m + y].pb((x - 1) * m + y);
        } if (y > 1) {
            adj[(x - 1) * m + y].pb((x - 1) * m + y - 1);
            adj[(x - 1) * m + y - 1].pb((x - 1) * m + y);
        } if (y < m) {
            adj[(x - 1) * m + y].pb((x - 1) * m + y + 1);
            adj[(x - 1) * m + y + 1].pb((x - 1) * m + y);
        }
    } idx = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!used[idx]) {
                vec.clear(); cur = 0;
                dfs((i - 1) * m + j);
                if (3 * cur > vec.size()) {
                    cout << "No"; return;
                } for (int v : vec) ans += v;
                if (3 * cur == vec.size() - 1) {
                    int mn = 1e9;
                    for (int v : vec)
                        mn = min(mn, v);
                    ans -= mn;
                }
            } idx++;
        }
    } cout << ans;
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
        cout << '\n';
    }
    return 0;
}

Compilation message (stderr)

covering.cpp: In function 'void solve()':
covering.cpp:70:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |                 if (3 * cur > vec.size()) {
      |                     ~~~~~~~~^~~~~~~~~~~~
covering.cpp:73:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |                 if (3 * cur == vec.size() - 1) {
      |                     ~~~~~~~~^~~~~~~~~~~~~~~~~

• 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