Submission #653178

#	Time	Username	Problem	Language	Result	Execution time	Memory
653178		ilia_rr	T-Covering (eJOI19_covering)	C++14	100 / 100	98 ms	23288 KiB

covering

// بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيمِ
// Written by Ilia Rahbar

// #pragma GCC optimize ("O3,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target ("abm,bmi,bmi2,tbm,avx2")

#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define ai(x) array <int, x>
#define F first 
#define S second

const int MOD = 1e9 + 7, N = 1e6 + 100;

int ans, n, m, xx, yy, k, ce, cv, mx, my, mv;

ai(2) h1[4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}, 
    h2[4] = {{1, 1}, {-1, -1}, {-1, 1}, {1, -1}}, 
    h3[4] = {{0, 2}, {0, -2}, {2, 0}, {-2, 0}};

ai(2) hh1[2] = {{0, 1}, {1, 0}}, hh2[2] = {{1, 1}, {1, -1}}, hh3[2] = {{0, 2}, {2, 0}}, hy3[2] = {{0, 2}, {0, -2}}, hx3[2] = {{2, 0}, {-2, 0}};

void no()
{
    cout << "No";

    exit(0);
}

inline bool ex(int x, int y)
{
    return (-1 < x && x < m && -1 < y && y < n);
}

void add(int x, int y, int **g)
{
    for (auto d : h1)
    {
        if (ex(x + d[0], y + d[1]) && !g[x + d[0]][y + d[1]])
        {
            g[x + d[0]][y + d[1]] = 2;
        }
    }
    
    if (g[x][y] == 3)
        no();

    g[x][y] = 3;
}

void dfs(int x, int y, int **g, int **c)
{
    add(x, y, g);

    for (auto d : h1)
    {
        if (ex(x + d[0], y + d[1]) && c[x + d[0]][y + d[1]] < mv)
        {
            mv = c[x + d[0]][y + d[1]];

            mx = x + d[0];

            my = y + d[1];
        }
    }

    cv++;

    for (auto d : h3)
    {
        if (ex(x + d[0], y + d[1]))
        {
            ce += (g[x + d[0]][y + d[1]] == 1 || g[x + d[0]][y + d[1]] == 3);

            if (g[x + d[0]][y + d[1]] == 1)
                dfs(x + d[0], y + d[1], g, c);
        }
    }
}

int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> m >> n;

    int **g, **c;

    g = new int *[m];
    c = new int *[m];

    for (int i = 0; i < m; i++)
    {
        g[i] = new int [n];
        c[i] = new int [n];
    }

    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> c[i][j];

    cin >> k;

    for (int i = 0; i < k; i++)
    {
        cin >> xx >> yy;

        g[xx][yy] = 1;
    }

    if (n < 2 || m < 2 || g[0][0] || g[0][n-1] || g[m-1][0] || g[m-1][n-1])
        no();
    
    for (int j = 0; j < n; j++)
    {
        if (g[0][j] != 1)
            continue;
        
        add(0, j, g);

        for (auto d : h1)
            if (ex(d[0], j + d[1]) && g[d[0]][j + d[1]] == 1)
                no();

        for (auto d : h2)
            if (ex(d[0], j + d[1]) && g[d[0]][j + d[1]] == 1)
                no();

        for (auto d : hy3)
            if (ex(d[0], j + d[1]) && g[d[0]][j + d[1]] == 1)
                no();
    }

    for (int j = 0; j < n; j++)
    {
        if (g[m - 1][j] != 1)
            continue;
        
        add(m-1, j, g);

        for (auto d : h1)
            if (ex(m - 1 + d[0], j + d[1]) && g[m - 1 + d[0]][j + d[1]] == 1)
                no();

        for (auto d : h2)
            if (ex(m - 1 + d[0], j + d[1]) && g[m - 1 + d[0]][j + d[1]] == 1)
                no();

        for (auto d : hy3)
            if (ex(m - 1 + d[0], j + d[1]) && g[m - 1 + d[0]][j + d[1]] == 1)
                no();
    }

    for (int i = 0; i < m; i++)
    {
        if (g[i][0] != 1)
            continue;

        add(i, 0, g);

        for (auto d : h1)
            if (ex(d[0] + i, d[1]) && g[d[0] + i][d[1]] == 1)
                no();

        for (auto d : h2)
            if (ex(d[0] + i, d[1]) && g[d[0] + i][d[1]] == 1)
                no();

        for (auto d : hx3)
            if (ex(d[0] + i, d[1]) && g[d[0] + i][d[1]] == 1)
                no();
    }

    for (int i = 0; i < m; i++)
    {
        if (g[i][n - 1] != 1)
            continue;

        add(i, n-1, g);

        for (auto d : h1)
            if (ex(d[0] + i, d[1] + n - 1) && g[d[0] + i][d[1] + n - 1] == 1)
                no();

        for (auto d : h2)
            if (ex(d[0] + i, d[1] + n - 1) && g[d[0] + i][d[1] + n - 1] == 1)
                no();

        for (auto d : hx3)
            if (ex(d[0] + i, d[1] + n - 1) && g[d[0] + i][d[1] + n - 1] == 1)
                no();
    }

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (g[i][j] != 1)
                continue;

            for (auto d : hh1)
                if (ex(i + d[0], j + d[1]) && g[i + d[0]][j + d[1]] == 1)
                {
                    add(i, j, g);
                    add(i + d[0], j + d[1], g);
                }

            for (auto d : hh2)
                if (ex(i + d[0], j + d[1]) && g[i + d[0]][j + d[1]] == 1)
                {
                    add(i, j, g);
                    add(i + d[0], j + d[1], g);
                }
        }   
    }

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (g[i][j] != 1)
                continue;

            for (auto d : h1)
                if (ex(i + d[0], j + d[1]) && g[i + d[0]][j + d[1]] == 3)
                    no();

            for (auto d : h2)
                if (ex(i + d[0], j + d[1]) && g[i + d[0]][j + d[1]] == 3)
                    no();
        }   
    }

    queue <ai(2)> q;

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (g[i][j] != 1)
                continue;

            for (auto d : h1)
            {
                if (ex(i + d[0], j + d[1]) && g[i + d[0]][j + d[1]] == 2)
                {
                    q.push({i, j});

                    break;   
                } 
            }
        }
    }

    while (q.size())
    {
        xx = q.front()[0];
        yy = q.front()[1];

        q.pop();

        add(xx, yy, g);

        for (auto d : h1)
        {
            if (ex(xx + d[0], yy + d[1]))
            {
                for (auto dd : h1)
                {
                    if (ex(xx + d[0] + dd[0], yy + d[1] + dd[1]) && g[xx + d[0] + dd[0]][yy + d[1] + dd[1]] == 1)
                        q.push({xx + d[0] + dd[0], yy + d[1] + dd[1]});
                }
            }
        }
    }

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (g[i][j] == 1)
            {
                ce = cv = 0;
                
                mx = my = mv = 1e9;

                dfs(i, j, g, c);

                ce /= 2;

                if (ce == cv - 1)
                    g[mx][my] = 0;

                if (ce > cv)
                    no();
            }
        }
    }

    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            ans += (g[i][j] ? c[i][j] : 0);

    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