Submission #456289

#	Time	Username	Problem	Language	Result	Execution time	Memory
456289		lukadupli	T-Covering (eJOI19_covering)	C++14	40 / 100	326 ms	81196 KiB

covering

#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

const int MAX = 1e6 + 5;

typedef pair <int, int> pii;

int n, m, k, sol;

vector <vector <int>> mat;
vector <vector <vector <int>>> occ;

pii specials[MAX];

set <int> ls[MAX];
set <pii> spec_set;
bool bio[MAX];

int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};

int mini;
pii dfs(int node){
    bio[node] = 1;

    int tiles = 0, visited = 0;

    for(int j = 0; j < 4; j++){
        int nx = specials[node].f + dx[j], ny = specials[node].s + dy[j];

        if(nx >= 0 && nx < n && ny >= 0 && ny < m && mat[nx][ny] != -1 && !spec_set.count({nx, ny})){
            tiles++;
            mini = min(mini, mat[nx][ny]);

            mat[nx][ny] = -1;
        }
    }

    for(int i : ls[node]){
        if(!bio[i]){
            pii info = dfs(i);

            visited += info.f;
            tiles += info.s;
        }
    }

    return {visited + 1, tiles};
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        mat.push_back({});
        occ.push_back({});
        for(int j = 0; j < m; j++){
            int e;
            cin >> e;
            mat[i].push_back(e);
            occ[i].push_back({});
        }
    }
    cin >> k;

    for(int i = 0; i < k; i++){
        int x, y;
        cin >> x >> y;

        specials[i] = {x, y};
        spec_set.insert({x, y});

        occ[x][y].push_back(i);
        for(int j = 0; j < 4; j++){
            int nx = x + dx[j], ny = y + dy[j];

            if(nx >= 0 && nx < n && ny >= 0 && ny < m) occ[nx][ny].push_back(i);
        }
    }

    int tile_cnt = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(!occ[i][j].empty()){
                tile_cnt++;
                sol += mat[i][j];

                for(int a = 0; a < occ[i][j].size(); a++){
                    for(int b = a + 1; b < occ[i][j].size(); b++){
                        ls[occ[i][j][a]].insert(occ[i][j][b]);
                        ls[occ[i][j][b]].insert(occ[i][j][a]);
                    }
                }
            }
        }
    }
    if(tile_cnt < k * 4){
        cout << "No";
        exit(0);
    }

    //cout << sol << '\n';
    for(int i = 0; i < k; i++){
        if(bio[i]) continue;

        //cout << i << ": ";

        mini = 2e9;

        pii info = dfs(i);

        //cout << info.f << ' ' << info.s << '\n';
        if(info.s != info.f * 3){
            sol -= mini;
        }
    }

    cout << sol;

    return 0;
}

Compilation message (stderr)

covering.cpp: In function 'int main()':
covering.cpp:92:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |                 for(int a = 0; a < occ[i][j].size(); a++){
      |                                ~~^~~~~~~~~~~~~~~~~~
covering.cpp:93:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |                     for(int b = a + 1; b < occ[i][j].size(); b++){
      |                                        ~~^~~~~~~~~~~~~~~~~~

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