Submission #1049714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049714		vjudge1	T-Covering (eJOI19_covering)	C++17	100 / 100	200 ms	53456 KiB

covering

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pi pair<int, int>
#define fi first
#define se second

const int N = 1e6 + 3;

int n, m, k, t, x, y, u, v;
ll ans = 0;
pi p[N];
vector<int> adj[N];
queue<pi> q;
priority_queue<int, vector<int>, greater<int> > pq;

int tx[4] = {0, 1, 0, -1}, ty[4] = {1, 0, -1, 0};

bool check (int u, int v) {
    return (0 <= u && u < n && 0 <= v && v < m);
}

pi toado (int k) {
    int x = k / m;
    int y = k % m;
    return {x, y};
}

int main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    vector<vector<int> > a(n + 1), d(n + 1);
    vector<vector<bool> > c(n + 1), vis(n + 1);

    for (int i = 0; i < n; ++ i) {
        a[i].resize(m + 1);
        d[i].resize(m + 1, 0);
        c[i].resize(m + 1, 0);
        vis[i].resize(m + 1, 0);
        for (int j = 0; j < m; ++ j) cin >> a[i][j];
    }

//    pi banh = toado(5);
//    cout << banh.fi << ' ' << banh.se << '\n';

    cin >> k;
    t = k;
    for (int i = 1; i <= k; ++ i) {
        cin >> p[i].fi >> p[i].se;
        tie(x, y) = p[i];
        c[x][y] = 1;
        d[x][y] ++;
        ans += a[x][y];
        int cnt = 0;
        for (int j = 0; j < 4; ++ j) {
            u = x + tx[j], v = y + ty[j];
            if (check(u, v))
                cnt ++,
                d[u][v] ++,
                ans += a[u][v],
                adj[x * m + y].push_back(u * m + v),
                adj[u * m + v].push_back(x * m + y);
        }

        if (cnt < 3) return cout << "No", 0;
    }

    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j < m; ++ j) {
            if (c[i][j] && !vis[i][j]) {
                vis[i][j] = 1;
                q.push({i, j});
                int S = 0, SN = 0, SD = 0;
                while (!q.empty()) {
                    tie(x, y) = q.front();
                    int t = d[x][y] - 1;
                    ans -= (t * a[x][y]);
                    S -= t;
                    if (!c[x][y]) pq.push(a[x][y]), SD ++;
                    else {
                        S ++, SN ++;
                        if (x == 0 || x == n - 1 || y == 0 || y == m - 1) S --;
                    }
                    q.pop();

//                    if (x == 0 || x == n - 1 || y == 0 || y == m - 1) S --;

                    for (int z : adj[x * m + y]) {
                        pi banh = toado(z);
                        tie(u, v) = banh;
                        if (!vis[u][v]) {
                            vis[u][v] = 1;
                            q.push({u, v});
                        }
                    }
                }


//                cout << SN << ' ' << SD << ' ' << S << '\n';

                while (!pq.empty()) {
                    if (S > 0) S --, ans -= pq.top(), SD --;
                    pq.pop();
                }


                if (S != 0 || SD != 3 * SN) return cout << "No", 0;
            }
        }
    }

    cout << ans;

    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