Submission #465717

#	Time	Username	Problem	Language	Result	Execution time	Memory
465717		Itamar	T-Covering (eJOI19_covering)	C++14	100 / 100	644 ms	19640 KiB

covering

using namespace std;
#include <iostream>
#include <vector>
#include <map>
#include <limits>
vector<vector<int>> num;
vector<vector<bool>> pain;
long long sum;
int n, m, k;
unsigned int mini = (int)-1;
vector<vector<bool>> blue;
map <pair<int, int>, bool> vis;
vector<pair<int, int>> vis1;
/*bool put(int i, int j, int d) {
    if (i == 0 && d != 4) {
        return 0;
    }
    if (i == m - 1 && d != 2) {
        return 0;
    }
    if (j == 0 && d != 1) {
        return 0;
    }
    if (j == n - 1 && d != 3) {
        return 0;
    }

    sum += num[i][j];
    cot[i][j] = 1;
    if (d % 2 == 1) {
        cot[i + 1][j] = 1;
        cot[i - 1][j] = 1;
        sum += num[i + 1][j];
        sum += num[i - 1][j];
    }
    else {
        cot[i][j + 1] = 1;
        cot[i][j - 1] = 1;
        sum += num[i][j + 1];
        sum += num[i][j - 1];
        if (d == 2) {
            sum += num[i - 1][j];
            cot[i - 1][j] = 1;
        }
    }

}*/

bool markBlue(int i, int j) {
    if (i < 0 || j < 0 || i >= m || j >= n || pain[i][j] || blue[i][j]) {
        return false;
    }
    blue[i][j] = true;
    if (num[i][j] < mini)
        mini = num[i][j];
    sum += num[i][j];
    return true;
}
bool check(int i, int j) {
    return !(i < 0 || j < 0 || i >= m || j >= n);
}
bool add(vector<pair<int, int>>& nut, int x, int y) {
    if (check(x, y) && pain[x][y] && !vis[{x, y}]) {
        nut.push_back({ x,y });
        vis[{x, y}] = 1;
        return true;
    }
    return false;
}
int main()
{

    cin >> m;
    cin >> n;
    sum = 0;

    pain.resize(m);
    num.resize(m);
    blue.resize(m);
    for (int i = 0; i < m; i++) {
        pain[i].resize(n);

        for (int j = 0; j < n; j++) {
            int x;
            cin >> x;
            num[i].push_back(x);
            blue[i].push_back(0);
        }
    }

    cin >> k;
    pair<int, int> rand;
    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x;
        cin >> y;
        vis[{ x, y }] = 0;
        vis1.push_back({ x,y });
        pain[x][y] = 1;
        rand = { x,y };
    }
    int blues = 0, reds = 1;
    bool flag = true;
    vector<pair<int, int>> nut;
    for (int i = 0; i < k; i++) {
        if (vis[vis1[i]])
            continue;
        nut.push_back(vis1[i]);
        vis[vis1[i]] = 1;
        while (nut.size() != 0) {
            int x = nut[nut.size() - 1].first, y = nut[nut.size() - 1].second;
            nut.pop_back();
            blues += markBlue(x - 1, y);
            blues += markBlue(x, y - 1);
            blues += markBlue(x + 1, y);
            blues += markBlue(x, y + 1);
            reds += add(nut, x - 2, y);
            reds += add(nut, x - 1, y);
            reds += add(nut, x + 1, y);
            reds += add(nut, x + 2, y);
            reds += add(nut, x - 1, y - 1);
            reds += add(nut, x - 1, y + 1);
            reds += add(nut, x + 1, y - 1);
            reds += add(nut, x + 1, y + 1);
            reds += add(nut, x, y - 2);
            reds += add(nut, x, y - 1);
            reds += add(nut, x, y + 1);
            reds += add(nut, x, y + 2);
            sum += num[x][y];
        }
        if (reds * 3 > blues) {
            cout << "No";
            flag = false;
            break;
        }
        if (reds * 3 + 1 == blues) {
            sum -= mini;
        }
        mini = (int)-1;
        blues = 0;
        reds = 1;
    }
    if (flag)
        cout << sum;
}

Compilation message (stderr)

covering.cpp: In function 'bool markBlue(int, int)':
covering.cpp:54:19: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'unsigned int' [-Wsign-compare]
   54 |     if (num[i][j] < mini)

• 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