Submission #1056674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056674		Nickpapadak	T-Covering (eJOI19_covering)	C++14	100 / 100	108 ms	53700 KiB

covering

#include<bits/stdc++.h>
using namespace std;
#define XX first
#define YY second
const unsigned int MAXK = 1e+6 + 10;
const unsigned int MAXMN = 1e+6 + 10;
const unsigned int INF = 1e+7 + 10;
vector<vector<int> > grid;
vector<vector<bool> > sgrid;
vector<pair<int,int> > special;
vector<vector<int> > adj(MAXMN, vector<int>());
int N,M, K;
 
int firsSub(){
    int ans = 0;
    // totalinc = 0/;
    for(int i = 0; i<K; ++i){
        int c = 0;
        int x = special[i].XX, y = special[i].YY;
        int u = 0,r=0,l=0,d=0;
        r += grid[x+1][y];
        r += grid[x][y+1];
        r += grid[x][y-1];
 
        l += grid[x-1][y];
        l += grid[x][y+1];
        l += grid[x][y-1];
 
        d += grid[x-1][y];
        d += grid[x+1][y];
        d += grid[x][y+1];
 
        u += grid[x-1][y];
        u += grid[x+1][y];
        u += grid[x][y-1];
        // int x = special[i].X, y = special[i].Y;
        ans += grid[x][y];
        if(x == 1 ||sgrid[x-1][y]){
            ans += r;
            c++;
        }
        if(x == M || sgrid[x+1][y]){
            ans += l;
            c++;
        }
        if(y == 1 || sgrid[x][y-1]){
            ans += d;
            c++;
        }
        if(y == N || sgrid[x][y+1]){
            ans += u;
            c++;
        }
        if(c>=2) return -1;
        // printf("c: %d  \n", c);
        if(sgrid[x+1][y+1] || sgrid[x-1][y+1]){
            return c == 0 ?u: -1;}
        if(sgrid[x+1][y-1] || sgrid[x-1][y+1]){
            return c == 0?d: -1;}
        if(c==1) continue;
        int best = max(l, r);
        best = max(best, u);
        ans += max(best, d);
        // printf("%d s\n", ans);
    }
    return ans;
}
int solve410(int i, vector<vector<bool> > sgrids, int ans);
 
int Rleft(int i, vector<vector<bool> > sgrids, int ans){
    int x = special[i].XX, y = special[i].YY;
    int u = y+1, d = y-1, r = x+1, l = x-1;
    if(sgrids[x][u] || sgrids[x][d] || sgrids[l][y]) return -1;
    ans += grid[x][y];
    ans += grid[x][u];
    sgrids[x][u] = 1;
    ans += grid[x][d];
    sgrids[x][d] = 1;
    ans += grid[l][y];
    sgrids[l][y] = 1;
    return solve410(i+1, sgrids, ans);
}
 
int Rright(int i, vector<vector<bool> > sgrids, int ans){
    int x = special[i].XX, y = special[i].YY;
    int u = y+1, d = y-1, r = x+1, l = x-1;
    if(sgrids[x][u] || sgrids[x][d] || sgrids[r][y]) return -1;
    ans += grid[x][y];
    ans += grid[x][u];
    sgrids[x][u] = 1;
    ans += grid[x][d];
    sgrids[x][d] = 1;
    ans += grid[r][y];
    sgrids[r][y] = 1;
    return solve410(i+1, sgrids, ans);
}
 
int Rup(int i, vector<vector<bool> > sgrids, int ans){
    int x = special[i].XX, y = special[i].YY;
    int u = y+1, d = y-1, r = x+1, l = x-1;
    if(sgrids[x][u] || sgrids[r][y] || sgrids[l][y]) return -1;
    ans += grid[x][y];
    ans += grid[x][u];
    sgrids[x][u] = 1;
    ans += grid[r][y];
    sgrids[r][y] = 1;
    ans += grid[l][y];
    sgrids[l][y] = 1;
    return solve410(i+1, sgrids, ans);
}
 
int Rdown(int i, vector<vector<bool> > sgrids, int ans){
    int x = special[i].XX, y = special[i].YY;
    int u = y+1, d = y-1, r = x+1, l = x-1;
    if(sgrids[r][y] || sgrids[x][d] || sgrids[l][y]) return -1;
    ans += grid[x][y];
    ans += grid[r][y];
    sgrids[r][y] = 1;
    ans += grid[x][d];
    sgrids[x][d] = 1;
    ans += grid[l][y];
    sgrids[l][y] = 1;
    return solve410(i+1, sgrids, ans);
}
 
int solve410(int i, vector<vector<bool> > sgrids, int ans){
    if(i>=K){
        // for(int y = 1;y<= N; ++y){
        //     for(int x = 1;x <= M; ++x)
        //         cout << sgrids[x][y] << ' ';
        //     printf("\n");
        // }
        
        return ans;
    }
    // int x = special[i].XX, y = special[i].YY;
    // int u = y+1, d = y-1, r = x+1, l = x-1;
    // printf("%d ", ans);
    return max(max(Rleft(i, sgrids, ans), Rright(i, sgrids, ans)),
    max(Rup(i, sgrids, ans), Rdown(i, sgrids, ans)));
}

int sameRow(){
    vector<vector<int> > dp(K+1, vector<int>(3, 0));
    vector<int> spec;
    for(int i = 0; i<K;++i){
        spec.push_back(grid[special[i].XX][special[i].YY]);
        grid[special[i].XX][special[i].YY] = -INF;
    }
    grid[0][special[0].YY] = -INF;
    grid[M+1][special[0].YY] = -INF;
    if(special[0].YY == 1 || special[0].YY == M){
        int px = -1, ans = 0;
        for(int i =0; i<K;++i){
            int x = special[i].XX, y = special[i].YY;
            if(x-px <= 2 || M==x) {
                // printf("%d %d", px, x);
                return -10;
            }
            ans += spec[i];
            ans += grid[x-1][y] + grid[x+1][y];
            ans += special[0].YY == 1? grid[x][y+1]: grid[x][y-1];
        }
        return ans;
    }
    for(int i = 1; i<=K;++i){
        int x = special[i-1].XX, y = special[i-1].YY;
        int px = i> 1? special[i-2].XX: 0; 
        if(x-px <= 2) dp[i][0] = dp[i-1][0] +spec[i-1]+grid[x-1][y]+grid[x][y+1]+grid[x][y-1];
        else          dp[i][0] = max(dp[i-1][0], max(dp[i-1][1], dp[i-1][2])) +spec[i-1]+grid[x-1][y]+grid[x][y+1]+grid[x][y-1];
        dp[i][1] = max(dp[i-1][0], max(dp[i-1][1], dp[i-1][2])) +spec[i-1]+grid[x+1][y]+grid[x][y+1]+grid[x][y-1];
        if(x-px > 2)
            dp[i][2] = max(dp[i-1][0], max(dp[i-1][1], dp[i-1][2])) + spec[i-1]+grid[x-1][y]+grid[x+1][y]+max(grid[x][y-1],grid[x][y+1]);
        else dp[i][2] = dp[i-1][0] + spec[i-1]+grid[x-1][y]+grid[x+1][y]+max(grid[x][y-1],grid[x][y+1]);
        // printf("%d %d\n", dp[i][0], dp[i][1]);
    }
    return max(dp[K][0],dp[K][1]);
}

const pair<int,int> IdToCoord(int id){return {id%M == 0?M:id%M,(id/M)+min(id%M, 1)};}
const int CoordToId(int x, int y){return (y-1)*M + x;}

int dx[] = {1, -1, 0, 0, 1, 1, -1, -1, 2, -2, 0, 0};
int dy[] = {0, 0, 1, -1, 1, -1, 1, -1, 0, 0, 2, -2};
int vis[MAXMN];

bool IsInBounds(int x, int y){
    return (x > 0 && x <= M && y > 0 && y <= N);
}
int total, smallest;
int dfs(int v, int p, int &sides){
    // if(vis[v]) return 0;
    // printf("%d ", v);
    vis[v]= true;
    adj[v].push_back(p);
    adj[p].push_back(v);
    int x = IdToCoord(v).XX, y = IdToCoord(v).YY;
    int cnt = 1;
    for(int i = 0; i<12;++i){
        int _x = x +dx[i], _y = y +dy[i];
        if(IsInBounds(_x,_y) && !vis[CoordToId(_x, _y)] && sgrid[_x][_y])
            cnt+=dfs(CoordToId(_x,_y), v, sides);
    }
    total += grid[x][y];
    for(int i = 0; i<4;++i){
        int _x = x +dx[i], _y = y+ dy[i];
        
        if(IsInBounds(_x,_y) && !vis[CoordToId(_x,_y)]){
            vis[CoordToId(_x,_y)] = true;
            // printf("%d %d:%d %d\n", x,y,_x, _y);
            sides += 1;
            total += grid[_x][_y];
            smallest = min(grid[_x][_y], smallest);
        }
    }
    return cnt;
}

void solve(){
    for(int i = 0; i< K;++i){
        
        int x = special[i].XX, y = special[i].YY;
        if(vis[CoordToId(x,y)]) continue;
        int sides = 0;
        smallest =INF;
        int cnt = dfs(CoordToId(x,y), 0, sides);
        if(sides < 3*cnt) {printf("No");return;}
        if(sides > 3*cnt) {total -= smallest;}
        // printf("%d\n", total);
    }
    printf("%d", total);
}

int main(){
    scanf("%d%d", &N,&M);// N = y M = x
    grid.resize(M+10, vector<int>(N+10, 0));
    sgrid.resize(M+10, vector<bool>(N+10,0));
    for(int y = 1; y <=N;++y){
        for(int x = 1; x <=M; ++x){
            scanf("%d", &grid[x][y]);
            // printf("done\n");
        }        
    }
    // for(int i = 1; i<= M; ++i){
    //     sgrid[i][0] = 1;
    //     sgrid[i][N+1] = 1;
    // }
    // for(int i = 1; i<=N;++i){
    //     sgrid[0][i] = 1;
    //     sgrid[M+1][i] = 1;
    // }
    scanf("%d", &K);
    // while(K--){
    //     int a, b;
    //     scanf("%d%d",&a,&b);
    //     printf("%d\n", CoordToId(a,b));
    //     int c;
    //     scanf("%d", &c);
    //     printf("%d %d\n", IdToCoord(c).XX, IdToCoord(c).YY);
    // }
    bool allOneLine = 1;
    for(int i = 1; i<=K; ++i){
        int a,b;
        scanf("%d%d", &a,&b);
        special.push_back({b+1,a+1});
        if(a+1 != special[0].YY) allOneLine = false;
        sgrid[b+1][a+1] = 1;
        // printf("%d\n", grid[a+1][b+1]);
    }
    solve();
    // int sides=0;
    // printf("\n cnt: %d", dfs(CoordToId(special[0].XX, special[0].YY), 0, sides));
    // printf("  %d\n", sides);
    // if(allOneLine){
    //     sort(special.begin(), special.end());
    //     int x =sameRow();
    //     if(x < 0) printf("No");
    //     else      printf("%d", x);
    // }
    // else if(K < 10){
    //     int sol =solve410(0, sgrid, 0);
    //     if(sol == -1) printf("No");
    //     else          printf("%d", sol);
 
    // }
    // else {
    // int sol = firsSub();
    // if(sol == -1) printf("No");
    // else          printf("%d\n", sol);
// }
    return 0;
}

Compilation message (stderr)

covering.cpp: In function 'int Rleft(int, std::vector<std::vector<bool> >, int)':
covering.cpp:72:27: warning: unused variable 'r' [-Wunused-variable]
   72 |     int u = y+1, d = y-1, r = x+1, l = x-1;
      |                           ^
covering.cpp: In function 'int Rright(int, std::vector<std::vector<bool> >, int)':
covering.cpp:86:36: warning: unused variable 'l' [-Wunused-variable]
   86 |     int u = y+1, d = y-1, r = x+1, l = x-1;
      |                                    ^
covering.cpp: In function 'int Rup(int, std::vector<std::vector<bool> >, int)':
covering.cpp:100:18: warning: unused variable 'd' [-Wunused-variable]
  100 |     int u = y+1, d = y-1, r = x+1, l = x-1;
      |                  ^
covering.cpp: In function 'int Rdown(int, std::vector<std::vector<bool> >, int)':
covering.cpp:114:9: warning: unused variable 'u' [-Wunused-variable]
  114 |     int u = y+1, d = y-1, r = x+1, l = x-1;
      |         ^
covering.cpp: In function 'int main()':
covering.cpp:261:10: warning: variable 'allOneLine' set but not used [-Wunused-but-set-variable]
  261 |     bool allOneLine = 1;
      |          ^~~~~~~~~~
covering.cpp:235:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  235 |     scanf("%d%d", &N,&M);// N = y M = x
      |     ~~~~~^~~~~~~~~~~~~~~
covering.cpp:240:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  240 |             scanf("%d", &grid[x][y]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~
covering.cpp:252:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  252 |     scanf("%d", &K);
      |     ~~~~~^~~~~~~~~~
covering.cpp:264:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  264 |         scanf("%d%d", &a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~

• 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