Submission #1059534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059534		vjudge1	T-Covering (eJOI19_covering)	C++17	100 / 100	70 ms	15580 KiB

covering

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define se second
#define fi first

const int ar = 1e6 + 5;

int m, n;
int k;
int x[ar], y[ar];
vector<vector<int>> a;
vector<vector<bool>> check;
vector<vector<bool>> t;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
queue<tuple<int, int, int>> qu;
int ans = 0;
int cnt1 = 0, cnt2 = 0;
void bfs()
{
    cnt1 = 0;
    cnt2 = 0;
    int mi = 1e9;
    while(qu.size())
    {
        auto [u, v, type] = qu.front();
        //cout << u << ' ' << v << '\n';
        ans += a[u][v];
        if (type) cnt1++;
        else cnt2++, mi = min(mi, a[u][v]);
        qu.pop();
        for (int i = 0; i <= 3; i++)
        {
            int x = u + dx[i];
            int y = v + dy[i];
            if (x < 0 || x >= m || y < 0 || y >= n) continue;
            if (check[x][y]) continue;
            if (!type && !t[x][y]) continue;
            check[x][y] = true;
            qu.push({x, y, t[x][y]});
        }
    }
    if (cnt2 < 3 * cnt1)
    {
        cout << "No";
        exit(0);
    }
    if (cnt2 == 3 * cnt1 + 1) ans -= mi;
    //cout << '\n';
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> m >> n;
    a.resize(m);
    check.resize(m);
    t.resize(m);
    for (int i = 0; i < m; i++) a[i].resize(n), check[i].resize(n), t[i].resize(n);
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) cin >> a[i][j];
    cin >> k;
    for (int i = 1; i <= k; i++)
    {
        cin >> x[i] >> y[i];
        t[x[i]][y[i]] = true;
    }
    //cout << '\n';
    for (int i = 1; i <= k; i++)
    {
        if (!check[x[i]][y[i]])
        {
            check[x[i]][y[i]] = true;
            qu.push({x[i], y[i], 1});
            bfs();
        }
    }
    cout << ans;
}

• 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