oj.uz

Submission #652196

# Submission time Handle Problem Language Result Execution time Memory
652196 2022-10-21T16:30:32 Z Kahou T-Covering (eJOI19_covering) C++14
100 / 100
 153 ms 102400 KB 
/* In the name of God, aka Allah */
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mk make_pair
#define endl '\n'
#define kill(x) if (x) return cout << "No" << endl, void()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int inf = 1e9 + 50;
const int N = 1e6 + 50;
int m, n, k;
vector<int> grid[N];
vector<bool> mark[N];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int dx2[] = {-1, 1, 1, -1};
int dy2[] = {1, 1, -1, -1};

ll ans;
int t;
int bk[N];
int mn[N];
vector<int> adj[N];
int vis[N];

bool val(int x, int y) {
        return x >= 1 && x <= m && y >= 1 && y <= n;
}

int f(int x, int y) {
        return (x-1)*n + y;
}

void dojob(int x, int y, int d) {
        ans += grid[x][y];
        mark[x][y] = 0;
        grid[x][y] = -inf;
        for (int i = 0; i < 4; i++) {
                if (i == d) continue;
                ans += grid[x+dx[i]][y+dy[i]];
                grid[x+dx[i]][y+dy[i]] = -inf;
        }
}

void dfs(int u, int p) {
        vis[u] = 1;
        int x = (u-1)/n+1, y = (u-1)%n+1;
        for (int i = 0; i < 4; i++) {
                mn[t] = min(grid[x+dx[i]][y+dy[i]], mn[t]);
        }
        for (int v:adj[u]) {
                if (v == p) continue;
                if (!vis[v]) dfs(v, u);
                else if (vis[v] == 1) bk[t]++;
        }
        vis[u] = 2;
}


void solve() {
        cin >> m >> n;
        for (int r = 0; r < m+5; r++) {
                grid[r].resize(n+5);
                mark[r].resize(n+5);
                for (int c = 0; c < n+5; c++) {
                        grid[r][c] = -inf;
                }
        }
        for (int r = 1; r <= m; r++) {
                for (int c = 1; c <= n; c++) {
                        cin >> grid[r][c];
                }
        }
        cin >> k;
        for (int i = 1; i <= k; i++) {
                int x, y;
                cin >> x >> y;
                x++, y++;
                mark[x][y] = 1;
        }

        for (int x = 1; x <= m; x++) {
                for (int y = 1; y <= n; y++) {
                        for (int i = 0; i < 4; i++) {
                                if (mark[x][y] && mark[x+dx[i]][y+dy[i]]) {
                                        dojob(x, y, i);
                                        dojob(x+dx[i], y+dy[i], (i+2)&3);
                                }
                                if (mark[x][y] && mark[x+dx2[i]][y+dy2[i]]) {
                                        dojob(x, y, i);
                                        dojob(x+dx2[i], y+dy2[i], (i+2)&3);
                                }
                        }
                }
        }
        for (int x = 1; x <= m; x++) {
                for (int y = 1; y <= n; y++) {
                        if (!mark[x][y]) continue;
                        ans += grid[x][y];
                        for (int i = 0; i < 4; i++) {
                                ans += grid[x+dx[i]][y+dy[i]];
                        }
                }
        }
        for (int x = 1; x <= m; x++) {
                for (int y = 1; y <= n; y++) {
                        for (int i = 0; i < 2; i++) {
                                if (val(x+2*dx[i], y+2*dy[i]) && mark[x][y] && mark[x+2*dx[i]][y+2*dy[i]]) {
                                        int u = f(x, y);
                                        int v = f(x+2*dx[i], y+2*dy[i]);
                                        ans -= grid[x+dx[i]][y+dy[i]];
                                        adj[u].push_back(v);
                                        adj[v].push_back(u);
                                }
                        }

                }
        }
        for (int x = 1; x <= m; x++) {
                for (int y = 1; y <= n; y++) {
                        if (mark[x][y]) {
                                int u = f(x,y);
                                if (vis[u]) continue;
                                t++;
                                mn[t] = inf;
                                dfs(u, u);
                                kill(bk[t] > 1);
                                if (!bk[t]) {
                                        ans -= mn[t];
                                }
                        }
                }
        }
        kill(ans < 0);
        cout << ans << endl;
}

int main() {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        solve();
        return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 86476 KB Output is correct
2 Correct 47 ms 86676 KB Output is correct
3 Correct 50 ms 87044 KB Output is correct
4 Correct 65 ms 88584 KB Output is correct
5 Correct 125 ms 93024 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 86412 KB Output is correct
2 Correct 44 ms 86596 KB Output is correct
3 Correct 50 ms 87012 KB Output is correct
4 Correct 64 ms 88648 KB Output is correct
5 Correct 119 ms 92996 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 86480 KB Output is correct
2 Correct 43 ms 86584 KB Output is correct
3 Correct 50 ms 87020 KB Output is correct
4 Correct 65 ms 88540 KB Output is correct
5 Correct 116 ms 92972 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 86532 KB Output is correct
2 Correct 44 ms 86336 KB Output is correct
3 Correct 44 ms 86740 KB Output is correct
4 Correct 45 ms 86592 KB Output is correct
5 Correct 48 ms 86988 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 86432 KB Output is correct
2 Correct 43 ms 86364 KB Output is correct
3 Correct 45 ms 86348 KB Output is correct
4 Correct 42 ms 86392 KB Output is correct
5 Correct 40 ms 86376 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 86476 KB Output is correct
2 Correct 47 ms 86676 KB Output is correct
3 Correct 50 ms 87044 KB Output is correct
4 Correct 65 ms 88584 KB Output is correct
5 Correct 125 ms 93024 KB Output is correct
6 Correct 42 ms 86412 KB Output is correct
7 Correct 44 ms 86596 KB Output is correct
8 Correct 50 ms 87012 KB Output is correct
9 Correct 64 ms 88648 KB Output is correct
10 Correct 119 ms 92996 KB Output is correct
11 Correct 43 ms 86480 KB Output is correct
12 Correct 43 ms 86584 KB Output is correct
13 Correct 50 ms 87020 KB Output is correct
14 Correct 65 ms 88540 KB Output is correct
15 Correct 116 ms 92972 KB Output is correct
16 Correct 42 ms 86532 KB Output is correct
17 Correct 44 ms 86336 KB Output is correct
18 Correct 44 ms 86740 KB Output is correct
19 Correct 45 ms 86592 KB Output is correct
20 Correct 48 ms 86988 KB Output is correct
21 Correct 49 ms 86484 KB Output is correct
22 Correct 45 ms 86660 KB Output is correct
23 Correct 49 ms 87140 KB Output is correct
24 Correct 61 ms 88552 KB Output is correct
25 Correct 114 ms 93100 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 86476 KB Output is correct
2 Correct 47 ms 86676 KB Output is correct
3 Correct 50 ms 87044 KB Output is correct
4 Correct 65 ms 88584 KB Output is correct
5 Correct 125 ms 93024 KB Output is correct
6 Correct 42 ms 86412 KB Output is correct
7 Correct 44 ms 86596 KB Output is correct
8 Correct 50 ms 87012 KB Output is correct
9 Correct 64 ms 88648 KB Output is correct
10 Correct 119 ms 92996 KB Output is correct
11 Correct 43 ms 86480 KB Output is correct
12 Correct 43 ms 86584 KB Output is correct
13 Correct 50 ms 87020 KB Output is correct
14 Correct 65 ms 88540 KB Output is correct
15 Correct 116 ms 92972 KB Output is correct
16 Correct 42 ms 86532 KB Output is correct
17 Correct 44 ms 86336 KB Output is correct
18 Correct 44 ms 86740 KB Output is correct
19 Correct 45 ms 86592 KB Output is correct
20 Correct 48 ms 86988 KB Output is correct
21 Correct 43 ms 86432 KB Output is correct
22 Correct 43 ms 86364 KB Output is correct
23 Correct 45 ms 86348 KB Output is correct
24 Correct 42 ms 86392 KB Output is correct
25 Correct 40 ms 86376 KB Output is correct
26 Correct 49 ms 86484 KB Output is correct
27 Correct 45 ms 86660 KB Output is correct
28 Correct 49 ms 87140 KB Output is correct
29 Correct 61 ms 88552 KB Output is correct
30 Correct 114 ms 93100 KB Output is correct
31 Correct 153 ms 102400 KB Output is correct
32 Correct 129 ms 96176 KB Output is correct
33 Correct 129 ms 100276 KB Output is correct
34 Correct 128 ms 95568 KB Output is correct
35 Correct 143 ms 102400 KB Output is correct