Submission #285013

#	Time	Username	Problem	Language	Result	Execution time	Memory
285013		WLZ	T-Covering (eJOI19_covering)	C++14	100 / 100	470 ms	32180 KiB

covering

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

const int INF = 0x3f3f3f3f;
const vector<int> dx = {0, 0, 1, -1};
const vector<int> dy = {1, -1, 0, 0};

int m, n;
vector< vector<int> > grid, special, g;
vector<int> r, c;
vector<bool> was;
set< pair<int, int> > st;
int sum, mn;

int dfs(int u) {
  was[u] = true;
  int ans = 1;
  sum += grid[r[u]][c[u]];
  for (int t = 0; t < 4; t++) {
    int nr = r[u] + dx[t];
    int nc = c[u] + dy[t];
    if (nr < 0 || nc < 0 || nr >= m || nc >= n) {
      continue;
    }
    if (!st.count({nr, nc}) && special[nr][nc] == -1) {
      st.insert({nr, nc});
      sum += grid[nr][nc];
      mn = min(mn, grid[nr][nc]);
    }
  }
  for (auto& v : g[u]) {
    if (!was[v]) {
      ans += dfs(v);
    }
  }
  return ans;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> m >> n;
  grid.assign(m, vector<int>(n));
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      cin >> grid[i][j];
    }
  }
  int k;
  cin >> k;
  special.assign(m, vector<int>(n, -1));
  r.resize(k);
  c.resize(k);
  for (int i = 0; i < k; i++) {
    cin >> r[i] >> c[i];
    special[r[i]][c[i]] = i;
  }
  g.resize(k);
  for (int i = 0; i < k; i++) {
    set<int> st;
    for (int t1 = 0; t1 < 4; t1++) {
      for (int t2 = 0; t2 < 4; t2++) {
        int nr = r[i] + dx[t1] + dx[t2];
        int nc = c[i] + dy[t1] + dy[t2];
        if (nr < 0 || nc < 0 || nr >= m || nc >= n) {
          continue;
        }
        st.insert(special[nr][nc]);
      }
      int nr = r[i] + dx[t1];
      int nc = c[i] + dy[t1];
      if (nr < 0 || nc < 0 || nr >= m || nc >= n) {
        continue;
      }
      st.insert(special[nr][nc]);
    }
    st.erase(i);
    st.erase(-1);
    for (auto& x : st) {
      g[i].push_back(x);
    }
  }
  was.assign(k, false);
  int ans = 0;
  for (int i = 0; i < k; i++) {
    if (!was[i]) {
      sum = 0; mn = INF;
      st.clear();
      int sz = dfs(i);
      if ((int) st.size() < 3 * sz) {
        cout << "No\n";
        return 0;
      } else if ((int) st.size() == 3 * sz) {
        ans += sum;
      } else {
        ans += sum - mn;
      }
    }
  }
  cout << ans << '\n';
  return 0;
}

• 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