Submission #447087

#	Time	Username	Problem	Language	Result	Execution time	Memory
447087		thebitninja	T-Covering (eJOI19_covering)	C++14	0 / 100	25 ms	1064 KiB

covering

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<vb> vvb;

pair<int,int> pom[4] = {{0,1}, {0,-1}, {1, 0}, {-1, 0}};
pair<int,int> pom2[8] = {{1,1}, {1,-1}, {-1, 1}, {-1, -1}, {0,2}, {0,-2}, {2, 0}, {-2, 0}};
pair<int,int> pom3[4] = {{0,2}, {0,-2}, {2, 0}, {-2, 0}};

bool edge(int r, int c, int n, int m){
    return (r==0 || r==n-1 || c==0 || c==m-1);
}

int getSum(int i, int n, int m, vvi& grid, vi& row, vi& col, vvb& taken){
    int res = grid[row[i]][col[i]];
    for(int p=0; p<4; p++){
        int r = row[i] + pom[p].first, 
            c = col[i] + pom[p].second; 
        if(r<0 || r>=n || c<0 || c>=m) continue;
        if(!taken[r][c])
            res += grid[r][c];
        taken[r][c] = true;
    }
    return res;
}

int getSumCount(int i, int n, int m, vvi& grid, vi& row, vi& col, vvb& taken, int& cnt, int& mr, int& mc){
    int res = grid[row[i]][col[i]];
    for(int p=0; p<4; p++){
        int r = row[i] + pom[p].first, 
            c = col[i] + pom[p].second; 
        if(r<0 || r>=n || c<0 || c>=m) continue;
        if(!taken[r][c]){
            res += grid[r][c];
            taken[r][c] = true;
            cnt++;
            if(mr == -1 || grid[r][c] < grid[mr][mc]){
                mr = r; mc = c;
            }
        }
    }
    return res;
}


int solve(int n, int m, vvi& grid, int k, vi& row, vi& col, vvi& cellidx){
    int res = 0;
    vb solved(k, false);
    vvb taken(n, vb(m, false));

    for(int i=0; i<k; i++)
        taken[row[i]][col[i]] = true;
    
    for(int i=0; i<k; i++){
        if(!solved[i]){
            for(int r=-1; r<=1; r++){
                for(int c=-1; c<=1; c++){
                    if(row[i]+r<0 || row[i]+r>=n || col[i]+c<0 || col[i]+c>=m)
                        continue;
                    if(r == 0 && c == 0) 
                        continue;
                    int ci = cellidx[row[i]+r][col[i]+c];
                    if(ci == -1)
                        continue;
                    if(solved[ci])
                        return -1;
                    if(edge(row[i], col[i], n, m) || edge(row[ci], col[ci], n, m))
                        return -1;
                    solved[i] = solved[ci] = true;
                    res += getSum(i, n, m, grid, row, col, taken);
                    res += getSum(ci, n, m, grid, row, col, taken);
                }
            }
        } 
    }

    stack<int> st;
    for(int i=0; i<k; i++){
        if(!solved[i]){
            int t = 0;
            for(int p=0; p<4; p++){
                int r = row[i] + pom[p].first, 
                    c = col[i] + pom[p].second; 
                if(r<0 || r>=n || c<0 || c>=m || taken[r][c]) t++;
            }
            if(t > 1) return -1;
            if(t == 1) st.push(i);
        }
    }

    while(!st.empty()){
        int i = st.top();
        st.pop();
        solved[i] = true;
        int t = 0;
        for(int p=0; p<4; p++){
            int r = row[i] + pom[p].first, 
                c = col[i] + pom[p].second; 
            if(r<0 || r>=n || c<0 || c>=m) {
                t++;
                continue;
            }
            if(taken[r][c]) t++;
            else {
                taken[r][c] = true;
                res += grid[r][c];
            }
        }
        if(t > 1) return -1;
        for(int p=0; p<8; p++){
            int r = row[i] + pom2[p].first, 
                c = col[i] + pom2[p].second; 
            if(r<0 || r>=n || c<0 || c>=m) continue;
            int ci = cellidx[r][c];
            if(ci != -1) st.push(ci);
        }
    }

    for(int i=0; i<k; i++){
        if(!solved[i]){
            vector<int> cmp;
            queue<int> q;
            q.push(i);
            while(!q.empty()){
                int v = q.front();
                q.pop();
                if(solved[v]) continue;
                solved[v] = true;
                cmp.push_back(v);
                for(int p=0; p<4; p++){
                    int r = row[i] + pom3[p].first,
                        c = col[i] + pom3[p].second;
                    if(r<0 || r>=n || c<0 || c>=m) continue;
                    int ci = cellidx[r][c];
                    if(ci != -1) q.push(ci);
                }
            }
            int cnt = 0, mr = -1, mc = -1;
            for(int j : cmp)
                res += getSumCount(j, n, m, grid, row, col, taken, cnt, mr, mc);
            if(cnt > 3*cmp.size()){
                res -= grid[mr][mc];
                taken[mr][mc] = false;
            } else if(cnt < 3*cmp.size())
                return -1;
        }
    }

    return res;
}

int main()
{
    int n, m;
    cin >> n >> m;
    vvi grid(n, vi(m));
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            cin >> grid[i][j];

    int k;
    cin >> k;
    vi row(k), col(k);
    vvi cellidx(n, vi(m, -1));
    for(int i=0; i<k; i++){
        cin >> row[i] >> col[i];
        cellidx[row[i]][col[i]] = i;
    }

    int res = solve(n, m, grid, k, row, col, cellidx);
    if(res == -1) cout << "No\n";
    else cout << res << '\n';

    return 0;
}

Compilation message (stderr)

covering.cpp: In function 'int solve(int, int, vvi&, int, vi&, vi&, vvi&)':
covering.cpp:144:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |             if(cnt > 3*cmp.size()){
      |                ~~~~^~~~~~~~~~~~~~
covering.cpp:147:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |             } else if(cnt < 3*cmp.size())
      |                       ~~~~^~~~~~~~~~~~~~

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