Submission #456301

#	Time	Username	Problem	Language	Result	Execution time	Memory
456301		lukadupli	T-Covering (eJOI19_covering)	C++14	100 / 100	985 ms	92372 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;

int mat[MAX];
vector <int> occ[MAX];

pii specials[MAX];

map <int, set <int>> ls;
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 * m + ny] != -1 && !spec_set.count({nx, ny})){
            tiles++;
            mini = min(mini, mat[nx * m + ny]);

            mat[nx * m + 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++){
        for(int j = 0; j < m; j++) cin >> mat[i * m + j];
    }
    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 * m + 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 * m + ny].push_back(i);
        }
    }

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

                for(int a = 0; a < occ[i * m + j].size(); a++){
                    for(int b = a + 1; b < occ[i * m + j].size(); b++){
                        ls[occ[i * m + j][a]].insert(occ[i * m + j][b]);
                        ls[occ[i * m + j][b]].insert(occ[i * m + j][a]);
                    }
                }
            }
        }
    }

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

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

        mini = 2e9;

        pii info = dfs(i);

        //assert(info.s >= info.f * 3);
        //cout << info.f << ' ' << info.s << '\n';

        if(info.s < info.f * 3){
            cout << "No";
            exit(0);
        }

        if(info.s > info.f * 3){
            sol -= mini;
        }
    }

    cout << sol;

    return 0;
}

Compilation message (stderr)

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

• 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