Submission #1049331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049331		Tam_theguide	T-Covering (eJOI19_covering)	C++17	100 / 100	60 ms	43836 KiB

covering

#include <bits/stdc++.h>
using namespace std;
const int Limit = 1e6;
const int LimitVal = 1000;
const int dirx[4] = {-1, 0, 1, 0};
const int diry[4] = {0, 1, 0, -1};
const int Cornerdirx[4] = {-1, 1, 1, -1};
const int Cornerdiry[4] = {1, 1, -1, -1};
int m, n, k;
vector<vector<int>> Grid, Status;
vector<int> Dsu;
bool InGrid(int& i, int& j) {
    return (0 <= i && i < m && 0 <= j && j < n);
}
int Zip(int& i, int& j) {
    return i * n + j;
}
int FindPar(int u) {
    if (u == Dsu[u]) return u;
    return Dsu[u] = FindPar(Dsu[u]);
}
bool Union(int u , int v) {
    u = FindPar(u);
    v = FindPar(v);
    if (u == v) return false;
    Dsu[v] = u;
    return true;
}
vector<pair<int, int>> Component[Limit];
vector<vector<bool>> isVisited;
vector<pair<int, int>> isVisited_RollBack;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> m >> n;
    Grid.resize(m + 1, vector<int>(n + 1));
    Status.resize(m + 1, vector<int>(n + 1));
    Dsu.resize(n * m + 1);
    for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
        cin >> Grid[i][j], Dsu[Zip(i, j)] = Zip(i, j);
    cin >> k;
    for (int i = 1; i <= k; i++) {
        int x, y;
        cin >> x >> y;
        Status[x][y] = true;
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (Status[i][j] == false) continue;
            for (int dir = 0; dir < 4; dir++) {
                pair<int, int> CloseAdj = {i + dirx[dir], j + diry[dir]};
                pair<int, int> FarAdj = {i + 2 * dirx[dir], j + 2 * diry[dir]};
                pair<int, int> CornerAdj = {i + Cornerdirx[dir], j + Cornerdiry[dir]};
                if (InGrid(CloseAdj.first, CloseAdj.second) && Status[CloseAdj.first][CloseAdj.second] == true)
                    Union(Zip(i, j), Zip(CloseAdj.first, CloseAdj.second));
                if (InGrid(FarAdj.first, FarAdj.second) && Status[FarAdj.first][FarAdj.second] == true)
                    Union(Zip(i, j), Zip(FarAdj.first, FarAdj.second));
                if (InGrid(CornerAdj.first, CornerAdj.second) && Status[CornerAdj.first][CornerAdj.second] == true)
                    Union(Zip(i, j), Zip(CornerAdj.first, CornerAdj.second));
            }
        }
    }

    for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
        if (Status[i][j] == true) 
            Component[FindPar(Zip(i, j))].emplace_back(i, j);
    int Ans = 0;
    isVisited.resize(m + 1, vector<bool>(n + 1));
    for (int i = 0; i < n * m; i++) {
        if (Component[i].empty()) continue;
        int CoverNum = 0, MaxSum = 0;

        for (auto& c: Component[i]) {
            MaxSum += Grid[c.first][c.second];
            for (int dir = 0; dir < 4; dir++) {
                int Cx = c.first + dirx[dir];
                int Cy = c.second + diry[dir];
                if (!InGrid(Cx, Cy) || Status[Cx][Cy] == true) continue;
                if (!isVisited[Cx][Cy]) {
                    isVisited[Cx][Cy] = true;
                    isVisited_RollBack.emplace_back(Cx, Cy);
                    CoverNum++;
                }
            }
        }

        if (CoverNum < 3 * (int)Component[i].size()) {
            cout << "No";
            return 0;
        } else if (CoverNum == 3 * (int)Component[i].size()) {
            for (auto& c: isVisited_RollBack)
                MaxSum += Grid[c.first][c.second];
        } else {
            int MinVal = LimitVal;
            
            for (auto& c: isVisited_RollBack) {
                MaxSum += Grid[c.first][c.second];
                MinVal = min(MinVal, Grid[c.first][c.second]);
            }
            MaxSum -= MinVal;
        }
        Ans += MaxSum;
        for (auto& c: isVisited_RollBack)
            isVisited[c.first][c.second] = 0;
        isVisited_RollBack.clear();
    }
    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