Submission #285575

#	Time	Username	Problem	Language	Result	Execution time	Memory
285575		alextodoran	T-Covering (eJOI19_covering)	C++17	100 / 100	131 ms	17212 KiB

covering

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int K_MAX = 1000002;

struct Cell
{
    int a, b;
};

int n, m;

vector <vector <int> > ma;

int k;

Cell v[K_MAX];

vector <vector <bool> > special;

bool inside (Cell c)
{
    return (1 <= c.a && c.a <= n && 1 <= c.b && c.b <= m);
}

vector <vector <int> > pos;

vector <vector <bool> > visited;

int da[] = {-1, 0, 1, 0}, db[] = {0, 1, 0, -1};

bool dfs (int a, int b)
{
    visited[a][b] = true;
    for(int d = 0; d < 4; d++)
        if(d != (pos[a][b] + 2) % 4)
        {
            int a1 = a + da[d] * 2, b1 = b + db[d] * 2;
            if(inside(Cell{a1, b1}) == false || special[a1][b1] == false)
                continue;
            if(pos[a1][b1] != -1 && pos[a1][b1] != d)
                return false;
            if(visited[a1][b1] == true)
                continue;
            pos[a1][b1] = d;
            if(dfs(a1, b1) == false)
                return false;
        }
    return true;
}

int mi;
int cntu, cnte;

void dfs1 (int a, int b)
{
    visited[a][b] = true;
    cntu++;
    for(int d = 0; d < 4; d++)
    {
        if(inside(Cell{a + da[d], b + db[d]}) == true)
            mi = min(mi, ma[a + da[d]][b + db[d]]);
        int a1 = a + da[d] * 2, b1 = b + db[d] * 2;
        if(inside(Cell{a1, b1}) == false || special[a1][b1] == false)
            continue;
        cnte++;
        if(visited[a1][b1] == true)
            continue;
        dfs1(a1, b1);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    ma.resize(n + 2);
    for(int i = 0; i <= n + 1; i++)
        ma[i].resize(m + 2);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> ma[i][j];
    cin >> k;
    for(int i = 1; i <= k; i++)
    {
        cin >> v[i].a >> v[i].b;
        v[i].a++;
        v[i].b++;
    }
    special.resize(n + 2);
    for(int i = 0; i <= n + 1; i++)
        special[i].resize(m + 2);
    for(int i = 1; i <= k; i++)
        special[v[i].a][v[i].b] = true;
    pos.resize(n + 2);
    for(int i = 0; i <= n + 1; i++)
        pos[i].resize(m + 2);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            pos[i][j] = -1;
    visited.resize(n + 2);
    for(int i = 0; i <= n + 1; i++)
        visited[i].resize(m + 2);
    for(int i = 1; i <= k; i++)
    {
        if((v[i].a == 1 || v[i].a == n) && (v[i].b == 1 || v[i].b == m))
        {
            cout << "No\n";
            return 0;
        }
        if(v[i].a == 1)
            pos[v[i].a][v[i].b] = 2;
        if(v[i].a == n)
            pos[v[i].a][v[i].b] = 0;
        if(v[i].b == 1)
            pos[v[i].a][v[i].b] = 1;
        if(v[i].b == m)
            pos[v[i].a][v[i].b] = 3;
        int aux = pos[v[i].a][v[i].b];
        int cnt = 0;
        if(inside(Cell{v[i].a - 1, v[i].b}) == true && special[v[i].a - 1][v[i].b] == true)
        {
            pos[v[i].a][v[i].b] = 2;
            cnt++;
        }
        if(inside(Cell{v[i].a + 1, v[i].b}) == true && special[v[i].a + 1][v[i].b] == true)
        {
            pos[v[i].a][v[i].b] = 0;
            cnt++;
        }
        if(inside(Cell{v[i].a, v[i].b - 1}) == true && special[v[i].a][v[i].b - 1] == true)
        {
            pos[v[i].a][v[i].b] = 1;
            cnt++;
        }
        if(inside(Cell{v[i].a, v[i].b + 1}) == true && special[v[i].a][v[i].b + 1] == true)
        {
            pos[v[i].a][v[i].b] = 3;
            cnt++;
        }
        if(cnt > 1 || (aux != -1 && pos[v[i].a][v[i].b] != aux))
        {
            cout << "No\n";
            return 0;
        }
    }
    for(int i = 1; i <= k; i++)
        if(pos[v[i].a][v[i].b] != -1 && visited[v[i].a][v[i].b] == false)
        {
            if(dfs(v[i].a, v[i].b) == false)
            {
                cout << "No\n";
                return 0;
            }
        }
    for(int i = 1; i <= k; i++)
    {
        if(inside(Cell{v[i].a - 1, v[i].b - 1}) == true && special[v[i].a - 1][v[i].b - 1] == true)
            pos[v[i].a][v[i].b] = 2;
        if(inside(Cell{v[i].a - 1, v[i].b + 1}) == true && special[v[i].a - 1][v[i].b + 1] == true)
            pos[v[i].a][v[i].b] = 2;
        int aux = pos[v[i].a][v[i].b];
        if(inside(Cell{v[i].a + 1, v[i].b - 1}) == true && special[v[i].a + 1][v[i].b - 1] == true)
            pos[v[i].a][v[i].b] = 0;
        if(inside(Cell{v[i].a + 1, v[i].b + 1}) == true && special[v[i].a + 1][v[i].b + 1] == true)
            pos[v[i].a][v[i].b] = 0;
        if(aux != -1 && aux != pos[v[i].a][v[i].b])
        {
            cout << "No\n";
            return 0;
        }
    }
    for(int i = 1; i <= k; i++)
        if(pos[v[i].a][v[i].b] != -1 && visited[v[i].a][v[i].b] == false)
        {
            if(dfs(v[i].a, v[i].b) == false)
            {
                cout << "No\n";
                return 0;
            }
        }
    int ans = 0;
    for(int i = 1; i <= k; i++)
        if(visited[v[i].a][v[i].b] == false)
        {
            cntu = cnte = 0;
            mi = INT_MAX;
            dfs1(v[i].a, v[i].b);
            cnte /= 2;
            if(cnte == cntu - 1)
                ans -= mi;
            else if(cnte > cntu)
            {
                cout << "No\n";
                return 0;
            }
        }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            if(special[i][j])
            {
                ans += ma[i][j];
                continue;
            }
            bool ok = false;
            for(int d = 0; d < 4; d++)
            {
                int i1 = i + da[d], j1 = j + db[d];
                if(inside(Cell{i1, j1}) == false)
                    continue;
                if(special[i1][j1] == true)
                    ok = true;
            }
            if(ok == true)
                ans += ma[i][j];
        }
    cout << ans << "\n";
    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