Submission #1221834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221834		khome	T-Covering (eJOI19_covering)	C++20	25 / 100	115 ms	8428 KiB

covering

#include <bits/stdc++.h>
using namespace std;
#define int long long

bool edge(int x, int y, int a, int b){
    if (a == x-1 && b == y-1) return true;               
    else if (a == x+1 && b == y+1) return true;               
    else if (a == x-1 && b == y) return true;               
    else if (a == x && b == y-1) return true;               
    else if (a == x+1 && b == y) return true;               
    else if (a == x && b == y+1) return true;               
    else if (a == x && b == y+2) return true;               
    else if (a == x && b == y-2) return true;               
    else if (a == x-2 && b == y) return true;               
    else if (a == x+2 && b == y) return true; 
    return false;
}

void solve(){
    int n, m; cin >> n >> m;
    vector<vector<int>> els(n, vector<int>(m));
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> els[i][j];
        }
    }
    
    int k; cin >> k;
    vector<pair<int, int>> xs;
    vector<bool> vis(k, false);
    for (int i = 0; i < k; i ++){
        int x, y; cin >> x >> y;
        xs.push_back({x, y});
    }
    
    int ans = 0;
    auto bfs = [&](int p) -> void {
        set<vector<int>> sosedi;
        int cnt = 0;

        queue<int> q;
        q.push(p); 
        int sz = 0;
        int mn = 1e9;

        while (!q.empty()){
            sz++;
            int p = q.front();
            vis[p] = true;
            q.pop();

            int x = xs[p].first, y = xs[p].second;

            if (sosedi.find({x, y}) == sosedi.end()) cnt+=els[x][y];
            sosedi.insert({x, y});

            if (x-1 >= 0 && sosedi.find({x-1, y}) == sosedi.end()) {
                sosedi.insert({x-1, y}); 
                cnt += els[x-1][y];
                mn = min(mn, els[x-1][y]);
            }
            
            if (x+1 < n && sosedi.find({x+1, y}) == sosedi.end()) {
                sosedi.insert({x+1, y}); 
                cnt += els[x+1][y];
                mn = min(mn, els[x+1][y]);
            }
            
            if (y-1 >= 0 && sosedi.find({x, y-1}) == sosedi.end()) {
                sosedi.insert({x, y-1}); 
                cnt += els[x][y-1];
                mn = min(mn, els[x][y-1]);
            }
            
            if (y+1 < m && sosedi.find({x, y+1}) == sosedi.end()) {
                sosedi.insert({x, y+1}); 
                cnt += els[x][y+1];
                mn = min(mn, els[x][y+1]);
            }

            for (int ch = 0; ch < k; ch ++) {
                if (p == ch) continue;
                int a = xs[ch].first, b = xs[ch].second;
                
                if (edge(x, y, a, b) && !vis[ch]) q.push(ch);
            }
        }
        // cout << sosedi.size() << ' ' << sz << ' ' << cnt << endl;
        if (sosedi.size() - sz < 3*sz) {cout << "No" << endl; exit(0);}
    
        if (sosedi.size() - sz == 3*sz) ans += cnt;
    
        if (sosedi.size() - sz == 3*sz + 1) ans += cnt - mn;
        return;
    };
        
    for (int i = 0; i < k; i++){
        int x = xs[i].first, y = xs[i].second;
        
        if (!vis[i]){
            bfs(i);
            // cout << 1<< endl;
        }
    
    }   
    
    cout << ans << endl;

}

signed main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
	int t = 1; 
    // cin >> t;
    while (t--)solve();
}

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