Submission #456300

#	Time	Username	Problem	Language	Result	Execution time	Memory
456300		lukadupli	T-Covering (eJOI19_covering)	C++14	Compilation error	0 ms	0 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 <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:19:14: error: wrong number of template arguments (1, should be at least 2)
   19 | map <set <int>> ls;
      |              ^~
In file included from /usr/include/c++/10/map:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:81,
                 from covering.cpp:1:
/usr/include/c++/10/bits/stl_map.h:100:11: note: provided for 'template<class _Key, class _Tp, class _Compare, class _Alloc> class std::map'
  100 |     class map
      |           ^~~
covering.cpp: In function 'pii dfs(int)':
covering.cpp:43:19: error: invalid types 'int[int]' for array subscript
   43 |     for(int i : ls[node]){
      |                   ^
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++){
      |                                        ~~^~~~~~~~~~~~~~~~~~~~~~~
covering.cpp:85:27: error: invalid types 'int[__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}]' for array subscript
   85 |                         ls[occ[i * m + j][a]].insert(occ[i * m + j][b]);
      |                           ^
covering.cpp:86:27: error: invalid types 'int[__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}]' for array subscript
   86 |                         ls[occ[i * m + j][b]].insert(occ[i * m + j][a]);
      |                           ^