Submission #237593

#	Time	Username	Problem	Language	Result	Execution time	Memory
237593		Half	T-Covering (eJOI19_covering)	C++14	10 / 100	37 ms	792 KiB

covering

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pi;
typedef long long ll;

#define loop(i,a,b) for (int i = a; i <= b; i++)

#define INF ((unsigned) ~0)
#define F first
#define S second
#define PB push_back
#define MP make_pair

int m, n, k;
ll res;
int a[1000000];
map<pi, int> sp;

int getA(int r, int c){
    if(n * r + c >= 0 && n * r + c < m * n)
        return a[n * r + c];
    return -1;
}

int& getAp(int r, int c){
    if(n * r + c >= 0 && n * r + c < m * n)
        return a[n * r + c];
    int x = -1;
    return x;
}

bool chkNgb(int r, int c){
    if(n * r + c < 0 || n * r + c >= m * n)
        return true;
    if(sp.count(MP(r, c)) == 0)
        return true;
    if(sp[MP(r, c)] > 0)
        return true;
    int dn = 0;
    if(getA(r + 1, c) == -1)
        dn++;
    if(getA(r - 1, c) == -1)
        dn++;
    if(getA(r, c + 1) == -1)
        dn++;
    if(getA(r, c - 1) == -1)
        dn++;
    if(dn >= 2)
        return false;
    if(dn == 1){
        res += max(getA(r + 1, c), 0);
        res += max(getA(r - 1, c), 0);
        res += max(getA(r, c + 1), 0);
        res += max(getA(r, c - 1), 0);
        getAp(r + 1, c) = -1;
        getAp(r - 1, c) = -1;
        getAp(r, c + 1) = -1;
        getAp(r, c - 1) = -1;
        sp[MP(r, c)] = 1;
        return chkNgb(r + 2, c) && chkNgb(r - 2, c) && chkNgb(r, c + 2) && chkNgb(r, c - 2);
    }
    if(sp.count(MP(r + 1, c + 1)) > 0){
        res += max(getA(r + 1, c), 0);
        res += max(getA(r - 1, c), 0);
        res += max(getA(r, c - 1), 0);
        getAp(r + 1, c) = -1;
        getAp(r - 1, c) = -1;
        getAp(r, c - 1) = -1;
        sp[MP(r, c)] = 1;
        return chkNgb(r + 2, c) && chkNgb(r - 2, c) && chkNgb(r, c + 2) && chkNgb(r, c - 2);
    }
    if(sp.count(MP(r - 1, c + 1)) > 0){
        res += max(getA(r + 1, c), 0);
        res += max(getA(r - 1, c), 0);
        res += max(getA(r, c - 1), 0);
        getAp(r + 1, c) = -1;
        getAp(r - 1, c) = -1;
        getAp(r, c - 1) = -1;
        sp[MP(r, c)] = 1;
        return chkNgb(r + 2, c) && chkNgb(r - 2, c) && chkNgb(r, c + 2) && chkNgb(r, c - 2);
    }
    if(sp.count(MP(r + 1, c - 1)) > 0){
        res += max(getA(r + 1, c), 0);
        res += max(getA(r - 1, c), 0);
        res += max(getA(r, c + 1), 0);
        getAp(r + 1, c) = -1;
        getAp(r - 1, c) = -1;
        getAp(r, c + 1) = -1;
        sp[MP(r, c)] = 1;
        return chkNgb(r + 2, c) && chkNgb(r - 2, c) && chkNgb(r, c + 2) && chkNgb(r, c - 2);
    }
    if(sp.count(MP(r - 1, c - 1)) > 0){
        res += max(getA(r + 1, c), 0);
        res += max(getA(r - 1, c), 0);
        res += max(getA(r, c + 1), 0);
        getAp(r + 1, c) = -1;
        getAp(r - 1, c) = -1;
        getAp(r, c + 1) = -1;
        sp[MP(r, c)] = 1;
        return chkNgb(r + 2, c) && chkNgb(r - 2, c) && chkNgb(r, c + 2) && chkNgb(r, c - 2);
    }
    return true;
}

pi dfs(int r, int c, int pr, int pc){
    if(n * r + c < 0 || n * r + c >= m * n || sp.count(MP(r, c)) == 0)
        return MP(0, 1001);
    if(sp[MP(r, c)] == 2){
        return MP(1, 1001);
    }
    sp[MP(r, c)] = 2;
    pi s = MP(0, 1001);
    for(int i = -1; i < 2; i += 2){
        for(int j = -1; j < 2; j += 2){
            if((r + i + j) != pr || (c + i - j) != pc){
                res += max(getA(r + (i + j)/2, c + (i - j)/2), 0);
                //cout << r + (i + j)/2 << " " << c + (i - j)/2 << ":" << getA(r + (i + j)/2, c + (i - j)/2) << "\n";
                s.S = min(s.S, getA(r + (i + j)/2, c + (i - j)/2));
                pi p = dfs(r + i + j, c + i - j, r, c);
                s = MP(max(s.F, p.F), min(s.S, p.S));
                getAp(r + (i + j)/2, c + (i - j)/2) = -1;
            }
        }
    }
    return s;
}

int main(){
    res = 0;
    cin >> m >> n;
    for(int r = 0; r < m; r++)
        for(int c = 0; c < n; c++)
            cin >> a[n * r + c];
    cin >> k;
    for(int i = 0; i < k; i++){
        int r, c;
        cin >> r >> c;
        sp[MP(r, c)] = 0;
        res += a[n * r + c];
        a[n * r + c] = -1;
    }
    for(map<pi, int>::iterator it = sp.begin(); it != sp.end(); it++){
        if(!chkNgb((it->F).F, (it->F).S)){
            cout << "No\n";
            return 0;
        }
    }
    //cout << res << "\n";
    for(map<pi, int>::iterator it = sp.begin(); it != sp.end(); it++){
        int r = (it->F).F;
        int c = (it->F).S;
        //cout << sp[MP(r, c)] << "\n";
        if(sp[MP(r, c)] == 0){
            pi p = dfs(r, c, -1, -1);
            //cout << p.F << "\n";
            if(p.F == 0)
                res -= p.S;
        }
    }
    cout << res << "\n";
}

Compilation message (stderr)

covering.cpp: In function 'int& getAp(int, int)':
covering.cpp:36:9: warning: reference to local variable 'x' returned [-Wreturn-local-addr]
     int x = -1;
         ^

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