Submission #1246113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246113		andrei_n	T-Covering (eJOI19_covering)	C++20	100 / 100	65 ms	21636 KiB

covering

#include <bits/stdc++.h>

#ifdef LOCAL
#include <debug.h>
#else
#define debug
#endif // LOCAL

using namespace std;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

vector<vector<int>> v;
vector<vector<int>> w;
vector<vector<int>> vis;
pair<int,int> fixQueue[1000005];
int fixIdx = 0;

void fixCell(int x, int y)
{
    w[x][y] = 2;
    fixQueue[fixIdx++] = make_pair(x, y);
}

int fix(int x, int y)
{
    int cnt = 0;
    if(w[x+1][y] == 0) fixCell(x+1, y); else ++cnt;
    if(w[x-1][y] == 0) fixCell(x-1, y); else ++cnt;
    if(w[x][y+1] == 0) fixCell(x, y+1); else ++cnt;
    if(w[x][y-1] == 0) fixCell(x, y-1); else ++cnt;
    w[x][y] = 2;
    return cnt;
}

void NO()
{
    cout<<"No";
    exit(0);
}

int edges, nodes;

void dfs(int x, int y)
{
    ++nodes;
    vis[x][y] = 1;
    for(int i=0; i<4; ++i)
        if(x+dx[i]*2 >= 0 && y+dy[i]*2 >= 0 && w[x+dx[i]*2][y+dy[i]*2] == 1)
        {
            ++edges;
            if(vis[x+dx[i]*2][y+dy[i]*2] == 0)
                dfs(x+dx[i]*2, y+dy[i]*2);
        }
}

void update(int i, int j, int limit = 1)
{
    if(w[i+1][j] || w[i-1][j] || w[i][j+1] || w[i][j-1])
    {
        if(fix(i, j) > limit) NO();
    }
    else if(w[i+1][j+1] == 1 || w[i+1][j-1] == 1 || w[i-1][j+1] == 1 || w[i-1][j-1] == 1)
    {
        if((w[i+1][j+1] == 1) + (w[i+1][j-1] == 1) + (w[i-1][j+1] == 1) + (w[i-1][j-1] == 1) > 1) NO();
        if(w[i+1][j+1] == 1) if(fix(i+1, j+1)) NO();
        if(w[i+1][j-1] == 1) if(fix(i+1, j-1)) NO();
        if(w[i-1][j+1] == 1) if(fix(i-1, j+1)) NO();
        if(w[i-1][j-1] == 1) if(fix(i-1, j-1)) NO();
        fix(i, j);
    }
    else return;
    int x = i, y = j;
    for(int i=0; i<4; ++i)
        if(x+dx[i]*2 >= 0 && y+dy[i]*2 >= 0 && w[x+dx[i]*2][y+dy[i]*2] == 1)
            update(x+dx[i]*2, y+dy[i]*2, limit);
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m, q; cin>>n>>m;
    v.assign(n+3, vector<int>(m+3, 0));
    w.assign(n+3, vector<int>(m+3, 0));
    vis.assign(n+3, vector<int>(m+3, 0));
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
            cin>>v[i][j];
    for(int i=0; i<=n+1; ++i)
        w[i][0] = w[i][m+1] = w[i][m+2] = 2;
    for(int i=0; i<=m+1; ++i)
        w[0][i] = w[n+1][i] = w[n+2][i] = 2;
    cin>>q;
    while(q--)
    {
        int x, y; cin>>x>>y;
        ++x; ++y;
        w[x][y] = 1;
    }
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
        {
            if(w[i][j] != 1) continue;
            update(i, j);
        }
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
        {
            if(w[i][j] != 1) continue;
            nodes = edges = 0;
            dfs(i, j);
            edges /= 2;
            if(edges > nodes) NO();
            if(edges == nodes)
            {
                w[i+1][j] = 2;
                update(i, j, 99);
            }
            else
            {
                int from = fixIdx;
                fixCell(i+1, j);
                update(i, j);
                int to = fixIdx;
                int minX = fixQueue[from].first, minY = fixQueue[from].second;
                for(int k=from+1; k<to; ++k)
                {
                    if(v[minX][minY] > v[fixQueue[k].first][fixQueue[k].second])
                    {
                        minX = fixQueue[k].first;
                        minY = fixQueue[k].second;
                    }
                }
                w[minX][minY] = 0;
            }
        }
    int ans = 0;
    for(int i=1; i<=n; ++i, debug("\n"))
        for(int j=1; j<=m; ++j)
        {
            if(w[i][j] == 1 || w[i][j] == 2)
                ans += v[i][j];
            debug("% ", w[i][j]);
        }
    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