Submission #283996

#TimeUsernameProblemLanguageResultExecution timeMemory
283996valerikkT-Covering (eJOI19_covering)C++17
100 / 100
298 ms33784 KiB
#include<bits/stdc++.h> using namespace std; #define F first #define S second #define pb push_back #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define pw(x) (1LL<<x) #define epr(...) fprintf(stderr, __VA_ARGS__); fflush(stderr) #define db(x) cerr << #x << " = " << x << '\n' #define db2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n"; #define db3(x, y, z) cerr << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", " << z << ")\n" #define dbv(a) cerr << #a << " = "; for (auto xxxx: a) cerr << xxxx << " "; cerr << '\n' typedef long long ll; typedef double dbl; const int INF = 1e9 + 17; const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; int solve(int n, int m, vector<vector<int>> a, int k, vector<pair<int, int>> t) { auto check = [&](int i, int j) { return i >= 0 && i < n && j >= 0 && j < m; }; vector<vector<int>> id(n, vector<int>(m, -1)); for (int i = 0; i < k; ++i) { id[t[i].F][t[i].S] = i; } vector<vector<int>> e(k); for (int i = 0; i < k; ++i) { for (int x = -2; x <= 2; ++x) { for (int y = -2; y <= 2; ++y) { pair<int,int> to = {t[i].F + x, t[i].S + y}; if (check(to.F, to.S) && abs(x) + abs(y) != 0 && abs(x) + abs(y) <= 2 && id[to.F][to.S] != -1) { e[i].pb(id[to.F][to.S]); } } } } vector<bool> used(k, false); vector<int> comp; function<void(int)> dfs = [&](int v) { used[v] = true; comp.pb(v); for (auto u: e[v]) { if (!used[u]) { dfs(u); } } }; int res = 0; for (int i = 0; i < k; ++i) { res += a[t[i].F][t[i].S]; } vector<vector<bool>> taken(n, vector<bool>(m, false)); for (int i = 0; i < k; ++i) { if (!used[i]) { comp = {}; dfs(i); vector<pair<int,int>> cur; for (auto v: comp) { for (int d = 0; d < 4; ++d) { pair<int,int> to = {t[v].F + dx[d], t[v].S + dy[d]}; if (check(to.F, to.S) && id[to.F][to.S] == -1 && !taken[to.F][to.S]) { taken[to.F][to.S] = true; cur.pb(to); } } } int need = sz(comp) * 3; if (sz(cur) < need) { return -INF; } for (auto it: cur) { res += a[it.F][it.S]; } if (sz(cur) > need) { int mn = INF; for (auto it: cur) { if (a[it.F][it.S] < mn) { mn = a[it.F][it.S]; } } res -= mn; } } } return res; } int main() { int n, m; scanf("%d %d", &n, &m); vector<vector<int>> a(n, vector<int>(m)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { scanf("%d", &a[i][j]); } } int k; scanf("%d", &k); vector<pair<int,int>> t(k); for (int i = 0; i < k; ++i) { scanf("%d %d", &t[i].F, &t[i].S); } int answer = solve(n, m, a, k, t); if (answer == -INF) { printf("No\n"); } else { printf("%d\n", answer); } return 0; }

Compilation message (stderr)

covering.cpp: In function 'int main()':
covering.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
covering.cpp:102:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |             scanf("%d", &a[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~
covering.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |     scanf("%d", &k);
      |     ~~~~~^~~~~~~~~~
covering.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  110 |         scanf("%d %d", &t[i].F, &t[i].S);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...