oj.uz

Submission #467914

# Submission time Handle Problem Language Result Execution time Memory
467914 2021-08-25T15:10:33 Z alontanay T-Covering (eJOI19_covering) C++14
55 / 100
 101 ms 12556 KB 
#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 == 0) {
        cout << "0" << endl;
        return 0;
    }
    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]) {
                            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 > 1 && xMap[b.y][b.x-2] && !group[b.y][b.x-2]) {
                            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]) {
                                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]) {
                                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]) {
                                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]) {
                                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]) {
                                gen.push_front({b.y,b.x+2});
                            }
                            if(b.y > 1 && xMap[b.y-2][b.x] && !group[b.y-2][b.x]) {
                                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]) {
                                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]) {
                                gen.push_front({b.y,b.x+2});
                            }
                            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});
                            }
                        }
                    }
                    
                    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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 10 ms 1848 KB Output is correct
4 Correct 29 ms 4292 KB Output is correct
5 Correct 97 ms 12436 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 4 ms 716 KB Output is correct
3 Correct 10 ms 1868 KB Output is correct
4 Correct 29 ms 4228 KB Output is correct
5 Correct 98 ms 12556 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 11 ms 1868 KB Output is correct
4 Correct 35 ms 4304 KB Output is correct
5 Correct 101 ms 12532 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 7 ms 1108 KB Output is correct
4 Correct 4 ms 716 KB Output is correct
5 Correct 11 ms 1900 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 10 ms 1848 KB Output is correct
4 Correct 29 ms 4292 KB Output is correct
5 Correct 97 ms 12436 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 4 ms 716 KB Output is correct
8 Correct 10 ms 1868 KB Output is correct
9 Correct 29 ms 4228 KB Output is correct
10 Correct 98 ms 12556 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 3 ms 716 KB Output is correct
13 Correct 11 ms 1868 KB Output is correct
14 Correct 35 ms 4304 KB Output is correct
15 Correct 101 ms 12532 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 7 ms 1108 KB Output is correct
19 Correct 4 ms 716 KB Output is correct
20 Correct 11 ms 1900 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 3 ms 716 KB Output is correct
23 Correct 10 ms 1868 KB Output is correct
24 Correct 31 ms 4268 KB Output is correct
25 Correct 96 ms 12440 KB Output is correct

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 10 ms 1848 KB Output is correct
4 Correct 29 ms 4292 KB Output is correct
5 Correct 97 ms 12436 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 4 ms 716 KB Output is correct
8 Correct 10 ms 1868 KB Output is correct
9 Correct 29 ms 4228 KB Output is correct
10 Correct 98 ms 12556 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 3 ms 716 KB Output is correct
13 Correct 11 ms 1868 KB Output is correct
14 Correct 35 ms 4304 KB Output is correct
15 Correct 101 ms 12532 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 7 ms 1108 KB Output is correct
19 Correct 4 ms 716 KB Output is correct
20 Correct 11 ms 1900 KB Output is correct
21 Incorrect 1 ms 204 KB Output isn't correct
22 Halted 0 ms 0 KB -