Submission #467910

#	Time	Username	Problem	Language	Result	Execution time	Memory
467910		alontanay	T-Covering (eJOI19_covering)	C++14	55 / 100	105 ms	15884 KiB

covering

#include <bits/stdc++.h>
#define ll long long
#define pi pair<int,int>
#define x second
#define y first

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n,m,k,x1,y1;
    cin >> n >> m;
    
    vector<vector<int>> board(n, vector<int>(m));
    for(int i = 0; i < n; i ++) {
        for(int j = 0; j < m; j ++) {
            cin >> board[i][j];
        }
    }
    cin >> k;
    if(k*4 > n*m || n == 1 || m == 1) {
        for(int i = 0; i < k; i ++) {
            cin >> x1 >> y1;
        }
        cout << "No" << endl;
        return 0;
    }
    vector<vector<int>> xMap(n, vector<int>(m));
    vector<vector<int>> group(n, vector<int>(m));
    for(int i = 0; i < k; i ++) {
        cin >> x1 >> y1;
        if(x1%(n-1) == 0 && y1%(n-1) == 0) {
            cout << "No" << endl;
            return 0;
        }
        xMap[x1][y1] = 1;
    }
    list<pi> gen;
    int curr_group = 0;
    vector<bool> groupType;

    for(int i = 0; i < n; i ++) {
        for(int j = 0; j < m; j ++) {
            if(xMap[i][j] && !group[i][j]) {
                curr_group ++;
                gen = {{i,j}};
                int curr_type = 1;
                while(!gen.empty()) {
                    pi b = gen.back();
                    group[b.y][b.x] = curr_group;
                    if(b.x == 0) {
                        curr_type --;
                        if(curr_type == -1) {
                            cout << "No" << endl;
                            return 0;
                        }
                        if(xMap[b.y+1][b.x] + xMap[b.y+1][b.x+1] + xMap[b.y][b.x+1] + xMap[b.y-1][b.x+1] + xMap[b.y-1][b.x] != 0) {
                            cout << "No" << endl;
                            return 0;
                        }
                        group[b.y+1][b.x] = curr_group;
                        group[b.y][b.x+1] = curr_group;
                        group[b.y-1][b.x] = curr_group;
                        if(b.y > 1 && xMap[b.y-2][b.x] && !group[b.y-2][b.x]) {
                            gen.push_front({b.y-2,b.x});
                        }
                        if(b.y < n - 2 && xMap[b.y+2][b.x] && !group[b.y+2][b.x]) {
                            gen.push_front({b.y+2,b.x});
                        }
                        if(b.x < m - 2 && xMap[b.y][b.x+2] && !group[b.y][b.x+2]) {
                            gen.push_front({b.y,b.x+2});
                        }
                        
                    } else if(b.x == m - 1) {
                        curr_type --;
                        if(curr_type == -1) {
                            cout << "No" << endl;
                            return 0;
                        }
                        if(xMap[b.y+1][b.x] + xMap[b.y+1][b.x-1] + xMap[b.y][b.x-1] + xMap[b.y-1][b.x-1] + xMap[b.y-1][b.x] != 0) {
                            cout << "No" << endl;
                            return 0;
                        }
                        group[b.y+1][b.x] = curr_group;
                        group[b.y][b.x-1] = curr_group;
                        group[b.y-1][b.x] = curr_group;
                        if(b.y > 1 && xMap[b.y-2][b.x] && !group[b.y-2][b.x]) {
                            group[b.y-2][b.x] = curr_group;
                            gen.push_front({b.y-2,b.x});
                        }
                        if(b.y < n - 2 && xMap[b.y+2][b.x] && !group[b.y+2][b.x]) {
                            group[b.y+2][b.x] = curr_group;
                            gen.push_front({b.y+2,b.x});
                        }
                        if(b.x > 1 && xMap[b.y][b.x-2] && !group[b.y][b.x-2]) {
                            group[b.y][b.x-2] = curr_group;
                            gen.push_front({b.y,b.x-2});
                        }
                    } else {
                        if(b.y == 0) {
                            curr_type --;
                            if(curr_type == -1) {
                                cout << "No" << endl;
                                return 0;
                            }
                            if(xMap[b.y][b.x+1] + xMap[b.y+1][b.x+1] + xMap[b.y+1][b.x] + xMap[b.y+1][b.x-1] + xMap[b.y][b.x-1] != 0) {
                                cout << "No" << endl;
                                return 0;
                            }
                            group[b.y][b.x+1] = curr_group;
                            group[b.y+1][b.x] = curr_group;
                            group[b.y][b.x-1] = curr_group;
                            if(b.x > 1 && xMap[b.y][b.x-2] && !group[b.y][b.x-2]) {
                                group[b.y][b.x-2] = curr_group;
                                gen.push_front({b.y,b.x-2});
                            }
                            if(b.x < m - 2 && xMap[b.y][b.x+2] && !group[b.y][b.x+2]) {
                                group[b.y][b.x+2] = curr_group;
                                gen.push_front({b.y,b.x+2});
                            }
                            if(b.y < n - 2 && xMap[b.y+2][b.x] && !group[b.y+2][b.x]) {
                                group[b.y+2][b.x] = curr_group;
                                gen.push_front({b.y+2,b.x});
                            }
                        
                        } else if(b.y == n - 1) {
                            curr_type --;
                            if(curr_type == -1) {
                                cout << "No" << endl;
                                return 0;
                            }
                            if(xMap[b.y][b.x+1] + xMap[b.y-1][b.x+1] + xMap[b.y-1][b.x] + xMap[b.y-1][b.x-1] + xMap[b.y][b.x-1] != 0) {
                                cout << "No" << endl;
                                return 0;
                            }
                            group[b.y][b.x+1] = curr_group;
                            group[b.y-1][b.x] = curr_group;
                            group[b.y][b.x-1] = curr_group;
                            if(b.x > 1 && xMap[b.y][b.x-2] && !group[b.y][b.x-2]) {
                                group[b.y][b.x-2] = curr_group;
                                gen.push_front({b.y,b.x-2});
                            }
                            if(b.x < m - 2 && xMap[b.y][b.x+2] && !group[b.y][b.x+2]) {
                                group[b.y][b.x+2] = curr_group;
                                gen.push_front({b.y,b.x+2});
                            }
                            if(b.y > 1 && xMap[b.y-2][b.x] && !group[b.y-2][b.x]) {
                                group[b.y-2][b.x] = curr_group;
                                gen.push_front({b.y-2,b.x});
                            }
                        
                        } else {
                            if(xMap[b.y][b.x+1] == 1 && !group[b.y][b.x+1]) {
                                curr_type --;
                                gen.push_front({b.y,b.x+1});
                            }
                            if(xMap[b.y+1][b.x+1] == 1 && !group[b.y+1][b.x+1]) {
                                curr_type --;
                                gen.push_front({b.y+1,b.x+1});
                            }
                            if(xMap[b.y+1][b.x] == 1 && !group[b.y+1][b.x]) {
                                curr_type --;
                                gen.push_front({b.y+1,b.x});
                            }
                            if(xMap[b.y+1][b.x-1] == 1 && !group[b.y+1][b.x-1]) {
                                curr_type --;
                                gen.push_front({b.y+1,b.x-1});
                            }
                            if(xMap[b.y][b.x-1] == 1 && !group[b.y][b.x-1]) {
                                curr_type --;
                                gen.push_front({b.y,b.x-1});
                            }
                            if(xMap[b.y-1][b.x-1] == 1 && !group[b.y-1][b.x-1]) {
                                curr_type --;
                                gen.push_front({b.y-1,b.x-1});
                            }
                            if(xMap[b.y-1][b.x] == 1 && !group[b.y-1][b.x]) {
                                curr_type --;
                                gen.push_front({b.y-1,b.x});
                            }
                            if(xMap[b.y-1][b.x+1] == 1 && !group[b.y-1][b.x+1]) {
                                curr_type --;
                                gen.push_front({b.y-1,b.x+1});
                            }
                            if(curr_type < 0) {
                                cout << "No" << endl;
                                return 0;
                            }
                            group[b.y][b.x+1] = curr_group;
                            group[b.y+1][b.x] = curr_group;
                            group[b.y][b.x-1] = curr_group;
                            group[b.y-1][b.x] = curr_group;
                            if(b.x > 1 && xMap[b.y][b.x-2] && !group[b.y][b.x-2]) {
                                group[b.y][b.x-2] = curr_group;
                                gen.push_front({b.y,b.x-2});
                            }
                            if(b.x < m - 2 && xMap[b.y][b.x+2] && !group[b.y][b.x+2]) {
                                group[b.y][b.x+2] = curr_group;
                                gen.push_front({b.y,b.x+2});
                            }
                            if(b.y > 1 && xMap[b.y-2][b.x] && !group[b.y-2][b.x]) {
                                group[b.y-2][b.x] = curr_group;
                                gen.push_front({b.y-2,b.x});
                            }
                            if(b.y < n - 2 && xMap[b.y+2][b.x] && !group[b.y+2][b.x]) {
                                group[b.y+2][b.x] = curr_group;
                                gen.push_front({b.y+2,b.x});
                            }
                        }
                    }
                    
                    gen.pop_back();
                }
                groupType.push_back(curr_type);
            }
        }
    }
    
    vector<ll> groupSizes(curr_group);
    vector<int> groupMins(curr_group, 1000000000);

    for(int i = 0; i < n; i ++) {
        for(int j = 0; j < m; j ++) {
            int g = group[i][j] - 1;
            if(g != -1) {
                groupSizes[g] += board[i][j];
                if(xMap[i][j] == 0) {
                    groupMins[g] = min(groupMins[g], board[i][j]);
                }
            }
        }
    }

    ll total = 0;
    for(int i = 0; i < curr_group; i ++) {
        if(groupType[i]) {
            total += groupSizes[i] - groupMins[i];
        } else {
            total += groupSizes[i];
        }
    }
    cout << total << endl;
    return 0;
}

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