Submission #641076

#	Time	Username	Problem	Language	Result	Execution time	Memory
641076		Tam_theguide	T-Covering (eJOI19_covering)	C++17	100 / 100	232 ms	76632 KiB

covering

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define pii pair<int, int>
#define print(x) cout<<"["<<(x)<<"]"
const int N = 1e6 + 5;
const pii E[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
const pii V[4] = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}};
const pii dt[4] = {{-2, 0}, {0, 2}, {2, 0}, {0, -2}};
int n , m , k;
vector<vector<int>> a, dfs_vis, cycle;
vector<vector<bool>> vis, red;
vector<vector<vector<pii>>> adj;
vector<vector<pii>> par;
set<pii> cycle_hit;
vector<pii> tree;
pii L[N];
void stop(){cout << "No"; exit(0);}
bool boundary(int i, int j){return (i == 1 || i == n || j == 1 || j == m);}
bool inside(int i, int j){return (1 <= i && i <= n && 1 <= j && j <= m);}
bool corner(int i, int j){return ((i == 1 || i == n) && (j == 1 || j == m));}
void dfs(int i_, int j_, int i, int j){
    if (dfs_vis[i][j] == 2) return;
    if (dfs_vis[i][j] == 1){
        pii tmp = {i_, j_};
        cycle[tmp.fi][tmp.se]++;
        while (!(tmp.fi == i && tmp.se == j)){
            pii xx = par[tmp.fi][tmp.se];
            tmp.fi = xx.fi;
            tmp.se = xx.se;
            cycle[tmp.fi][tmp.se]++;
        }
        return;
    }
    dfs_vis[i][j] = 1;
    par[i][j] = {i_, j_};
    for (auto c: adj[i][j]){
        if (c == par[i][j]) continue;
        dfs(i, j, c.fi, c.se);
    }
    dfs_vis[i][j] = 2;
}
int cnt;
void dfs2(int i_, int j_, int i, int j){
    cnt++;
    for (int t = 0; t < 4; t++){
        int u = i + E[t].fi;
        int v = j + E[t].se;
        if (!vis[u][v]) tree.pb({u, v});
    }
    dfs_vis[i][j] = 3;
    for (auto c: adj[i][j]){
        if (!red[c.fi][c.se] || (c.fi == i_ && c.se == j_))
            continue;
        dfs2(i, j, c.fi, c.se);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    a.resize(n + 2, vector<int>(m + 2));
    dfs_vis.resize(n + 2, vector<int>(m + 2, 0));
    vis.resize(n + 2, vector<bool>(m + 2, false));
    red.resize(n + 2, vector<bool>(m + 2, false));
    cycle.resize(n + 2, vector<int>(m + 2, 0));
    adj.resize(n + 2, vector<vector<pii>>(m + 2));
    par.resize(n + 2, vector<pii>(m + 2));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    cin >> k;
    for (int i = 1; i <= k; i++){
        cin >> L[i].fi >> L[i].se;
        L[i].fi++; L[i].se++;
        int u = L[i].fi, v = L[i].se;
        vis[u][v] = true; red[u][v] = true;
    }
    for (int i = 1; i <= k; i++){
        int u = L[i].fi, v = L[i].se;
        if (boundary(u, v)){
            if (corner(u, v)) stop();
            for (int t = 0; t < 4; t++){
                int u_ = u + E[t].fi;
                int v_ = v + E[t].se;
                if (inside(u_, v_)){
                    if (vis[u_][v_]) stop();
                    vis[u_][v_] = true;
                }
            }
            red[u][v] = false;
        }
    }
    // boundary-> done
    for (int u = 1; u <= n; u++)
        for (int v = 1; v <= m; v++){
            if (red[u][v]){
                for (int t = 1; t <= 2; t++){
                    int u_ = u + E[t].fi;
                    int v_ = v + E[t].se;
                    if (red[u_][v_]){
                        set<pii> tmp;
                        tmp.insert({u, v}); tmp.insert({u_, v_});
                        for (int tt = 0; tt < 4; tt++){
                            int u__ = u_ + E[tt].fi;
                            int v__ = v_ + E[tt].se;
                            tmp.insert({u__, v__});
                        }
                        for (int tt = 0; tt < 4; tt++){
                            int _u_ = u + E[tt].fi;
                            int _v_ = v + E[tt].se;
                            tmp.insert({_u_, _v_});
                        }
                        if (tmp.size() != 8) stop();
                        for (auto c: tmp){
                            if (!(c.fi == u && c.se == v) &&
                                !(c.fi == u_ && c.se == v_) && vis[c.fi][c.se]) stop();
                            vis[c.fi][c.se] = true;
                        }
                        red[u][v] = red[u_][v_] = false;
                    }
                }
            }
        }
    // edge -> done
    for (int u = 1; u <= n; u++)
        for (int v = 1; v <= m; v++){
            if (red[u][v]){
                for (int t = 1; t <= 2; t++){
                    int u_ = u + V[t].fi;
                    int v_ = v + V[t].se;
                    if (red[u_][v_]){
                        set<pii> tmp;
                        tmp.insert({u, v}); tmp.insert({u_, v_});
                        for (int tt = 0; tt < 4; tt++){
                            int u__ = u_ + E[tt].fi;
                            int v__ = v_ + E[tt].se;
                            tmp.insert({u__, v__});
                        }
                        for (int tt = 0; tt < 4; tt++){
                            int _u_ = u + E[tt].fi;
                            int _v_ = v + E[tt].se;
                            tmp.insert({_u_, _v_});
                        }
                        if (tmp.size() != 8) stop();
                        for (auto c: tmp){
                            if (!(c.fi == u && c.se == v) &&
                                !(c.fi == u_ && c.se == v_) && vis[c.fi][c.se]) stop();
                            vis[c.fi][c.se] = true;
                        }
                        red[u][v] = red[u_][v_] = false;
                    }
                }
            }
        }
    // vertice -> done
    for (int u = 1; u <= n; u++)
        for (int v = 1; v <= m; v++){
            if (red[u][v]){
                for (int t = 0; t < 4; t++){
                    int u_ = u + dt[t].fi;
                    int v_ = v + dt[t].se;
                    if (!inside(u_, v_)) continue;
                    if (red[u_][v_]) adj[u][v].pb({u_, v_});
                }
            }
        }
    for (int u = 1; u <= n; u++)
        for (int v = 1; v <= m; v++){
            if (red[u][v] && dfs_vis[u][v] != 2){
                dfs(0, 0, u, v);
            }
        }
    for (int u = 1; u <= n; u++)
        for (int v = 1; v <= m; v++)
            if (cycle[u][v]){
                if (cycle[u][v] > 1) stop();
                for (int t = 0; t < 4; t++){
                    int u_ = u + E[t].fi;
                    int v_ = v + E[t].se;
                    cycle_hit.insert({u_, v_});
                }
                red[u][v] = false;
            }
    for (auto c: cycle_hit){
        if (vis[c.fi][c.se]) stop();
        vis[c.fi][c.se] = true;
    }
    // cycle -> done;
    for (int u = 1; u <= n; u++)
        for (int v = 1; v <= m; v++){
            if (red[u][v] && dfs_vis[u][v] != 3){
                tree.clear(); cnt = 0;
                dfs2(0, 0, u, v);
                sort(tree.begin(), tree.end());
                tree.erase(unique(tree.begin(), tree.end()), tree.end());
                int Tr = (int)tree.size();
                if (Tr < 3 * cnt || Tr > 3 * cnt + 1) stop();
                if (Tr == 3 * cnt + 1){
                    sort(tree.begin(), tree.end(), [&](pii x, pii y){
                         return a[x.fi][x.se] < a[y.fi][y.se];
                    });
                    for (int i = 1; i < tree.size(); i++)
                        vis[tree[i].fi][tree[i].se] = true;
                }else{
                    for (auto c: tree)
                        vis[c.fi][c.se] = true;
                }
            }
        }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (vis[i][j]) ans += a[i][j];
    /*
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (vis[i][j]) print("x");
            else print("o");
        }
        cout << '\n';
    }
    */
    cout << ans;
}

Compilation message (stderr)

covering.cpp: In function 'int main()':
covering.cpp:205:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  205 |                     for (int i = 1; i < tree.size(); i++)
      |                                     ~~^~~~~~~~~~~~~

• 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