Submission #1221853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221853		veham	T-Covering (eJOI19_covering)	C++20	25 / 100	112 ms	8208 KiB

covering

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;

const vi X8 = {1,1,1,0,-1,-1,-1,0};
const vi Y8 = {-1,0,1,1,1,0,-1,-1};
const vi X4 = {2,0,-2,0};
const vi Y4 = {0,2,0,-2};

int DFS1(vvi &nei, vb &vis, int v, int prev = -1){
    int g = 0;
    vis[v] = 1;
    for(int u : nei[v]){
        if(u == prev) continue;
        if(vis[u]){
            if(u > v) g++;
            continue;
        }
        g += DFS1(nei,vis,u,v);
    }
    return g;
}

pair<ll,int> DFS2(vvi &nei, vb &vis, vi &R, vi &C, vvi &B, int v){
    ll s = 0;
    int m = 1000;
    vis[v] = 1;
    pair<ll,int> t;
    vi O(4,2);
    for(int u : nei[v]){
        if(!vis[u]){
            t = DFS2(nei,vis,R,C,B,u);
            s += t.first;
            m = min(m,t.second);
        }

        if(R[v] == R[u]){
            if(C[u] == C[v] + 2) O[0] = 1;
            if(C[u] == C[v] + 1) O[0] = 0;
            if(C[u] == C[v] - 1) O[2] = 0;
            if(C[u] == C[v] - 2) O[2] = 0;
        }
        else if(C[v] == C[u]){
            if(R[u] == R[v] + 1) O[1] = 0;
            if(R[u] == R[v] + 2) O[1] = 1;
            if(R[u] == R[v] - 1) O[3] = 0;
            if(R[u] == R[v] - 2) O[3] = 0;
        }
        else{
            if(R[u] == R[v] + 1) O[1] = 1;
            else O[3] = 1;
            if(C[u] == C[v] + 1) O[0] = 0;
            else O[2] = 0;
        }
    }
    for(int i = 0;i < 4;i++){
        if(R[v] + Y4[i]/2 < 0 || R[v] + Y4[i]/2 >= B.size() || C[v] + X4[i]/2 < 0 || C[v] + X4[i]/2 >= B[0].size())
            continue;
        if(O[i] == 2){
            m = min(m,B[R[v] + Y4[i]/2][C[v] + X4[i]/2]);
        }
        if(O[i]){
            s += B[R[v] + Y4[i]/2][C[v] + X4[i]/2];
        }
    }
    return {s,m};
}

int Calc(int m, int n, vvi &B, int k, vi &R, vi &C){
    vvi P(m,vi(n,-1));
    for(int i = 0;i < k;i++) P[R[i]][C[i]] = i;
    ll ans = 0;
    vb vis(k+1,0), vis2 = vis;
    vis[k] = 1;
    vvi nei(k),nei2 = nei;
    for(int i = 0;i < k;i++){
        ans += B[R[i]][C[i]];
        for(int j = 0;j < 8;j++){
            if(R[i] + Y8[j] < 0 || R[i] + Y8[j] >= m){
                if(X8[j] == 0) nei[i].push_back(k);
                continue;
            }
            if(C[i] + X8[j] < 0 || C[i] + X8[j] >= n){
                if(Y8[j] == 0) nei[i].push_back(k);
                continue;
            }
            if(P[R[i] + Y8[j]][C[i] + X8[j]] != -1){
                nei[i].push_back(P[R[i] + Y8[j]][C[i] + X8[j]]);
                nei2[i].push_back(P[R[i] + Y8[j]][C[i] + X8[j]]);
                if(j < 4) nei[i].push_back(k);
            }
        }
        for(int j = 0;j < 4;j++){
            if(R[i] + Y4[j] < 0 || R[i] + Y4[j] >= m) continue;
            if(C[i] + X4[j] < 0 || C[i] + X4[j] >= n) continue;
            if(P[R[i] + Y4[j]][C[i] + X4[j]] != -1){
                nei[i].push_back(P[R[i] + Y4[j]][C[i] + X4[j]]);
                nei2[i].push_back(P[R[i] + Y4[j]][C[i] + X4[j]]);
            }
        }
    }
    int g;
    pair<ll,int> pt;
    for(int i = 0;i < k;i++){
        if(vis[i]) continue;
        g = DFS1(nei,vis,i);
        if(g >= 2) return -1;
        pt = DFS2(nei2,vis2,R,C,B,i);
        ans += pt.first;
        if(g == 0) ans -= pt.second;
    }
    return ans;
}

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

    int ans = Calc(m,n,B,k,R,C);
    if(ans == -1) cout << "No";
    else cout << ans;
    return 0;
}

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