Submission #467167

#	Time	Username	Problem	Language	Result	Execution time	Memory
467167		mtxas	T-Covering (eJOI19_covering)	C++14	100 / 100	172 ms	63584 KiB

covering

#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
#define pll pair<ll, ll>
#define mii map<int, int>
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(x) ((int)x.size())
#define turbo() cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false)
#define _fre() freopen("input.txt", "r", stdin)
#define _for(a, b, c) for(int (a) = (b); (a) < (c); (a)++)
#define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); (a)++)
#define _forneq(a, b, c) for(int (a) = (b); (a) >= (c); (a)--)
#define _forn(a, b, c) for(int (a) = (b); (a) > (c); (a)--)
using namespace std;
#define int ll
#define MyMin(a, b) if(a>b) a= b;
/**********************************************************************************
                                STRUCTS
**********************************************************************************/

/**********************************************************************************
                               VARIABLES
**********************************************************************************/
int n, m, k, ans = 0;
bool pos = 1;
const int inf = 0x3f3f3f3f;
vector<vi> table;
vector<pii> specials;
vector<vi> col;
vector<vector<bool>> isSpecial;
vector<int> colCnt;
vector<int> colSum;
vector<int> colMin;
vector<int> p;
vector<int> dydis;
int dy[12] = {-1, 0, 1, 0, -2, -1, 0, 1, 2, 1, 0, -1};
int dx[12] = {0, 1, 0, -1, 0, 1, 2, 1, 0, -1, -2, -1};
/**********************************************************************************
                               FUNCTIONS
**********************************************************************************/
int cellId(int r, int c){
    //assert(n*(r-1) + c <= m*n);
    return m*(r-1) + c;
}
bool inRange(int r, int c){
    return 1 <= r && r<=n && 1<=c && c<=m;
}
void prepVectors(){
    colCnt.resize(m*n+1);
    colSum.resize(m*n+1);
    colMin.resize(m*n+1, inf);
    isSpecial.resize(n+2, vector<bool>(m+2, 0));
    col.resize(n+2, vi(m+2, 0));
    dydis.resize(m*n+1);
    p.resize(m*n+1, 0);
}
void prepTable(){
    table.resize(n+2, vi(m+2, 0));
    _foreq(i, 1, n) _foreq(j, 1, m) cin>>table[i][j];
}
void getSpecialCells(){
    cin>>k;
    _for(i, 0, k) {
        int r, c; cin>>r>>c; r++, c++;
        specials.pb({r, c});
    }
    for(auto [r, c]: specials)
        isSpecial[r][c] = 1;
}
void prepDsu(){
    for(auto [r, c]: specials)
        p[cellId(r, c)] = cellId(r, c);
    _foreq(i, 1, m*n) dydis[i] = 1;
}
void readInput(){
    cin>>n>>m;
    prepTable();
    prepVectors();
    getSpecialCells();
    prepDsu();
}
int finder(int x){
    if(p[x] == x) return x;
    return p[x] = finder(p[x]);
}
bool same(int a, int b){return finder(a) == finder(b);}
void unite(int a, int b){
    a = finder(a);
    b = finder(b);
    if(same(a, b)) return;
    p[a] = b;
    dydis[b] += dydis[a];
}
void uniteComps(){
    for(auto [r, c]: specials)
        _for(dir, 0, 12){
            int rr = r + dy[dir], cc = c+dx[dir];
            if(inRange(rr, cc))
                if(isSpecial[rr][cc])
                    unite(
                          cellId(r, c),
                          cellId(rr, cc)
                          );

        }
}
void colorTable(){
    for(auto [r, c]: specials){
        int color = finder(cellId(r, c));
       // assert(color <= m*n);
        _for(dir, 0, 4){
            int rr = r + dy[dir], cc = c+dx[dir];
            //assert(rr <= n+1 && cc <= m+1);
            col[rr][cc] = color;
        }
        col[r][c] = color;
    }
     _foreq(i, 1, n) _foreq(j, 1, m){
        if(col[i][j] > 0){
            int c = col[i][j];
           // assert(c <= m*n);
            colCnt[c]++;
            colSum[c] += table[i][j];
            if(!isSpecial[i][j]) MyMin(colMin[c], table[i][j]);
        }
     }

//     cout<<"color table:\n";
//     _foreq(i, 1, n){
//        _foreq(j, 1, m) cout<<col[i][j]<<" "<<(col[i][j] < 10 ? " ":""); cout<<'\n';
//     }
//     cout<<"actual table:\n";
//     _foreq(i, 1, n){
//        _foreq(j, 1, m) cout<<table[i][j]<<" "<<(table[i][j] < 10 ? " ":""); cout<<'\n';
//     }
//     cout<<"cellId's:\n";
//     _foreq(i, 1, n){
//        _foreq(j, 1, m) cout<<cellId(i, j)<<" "<<(cellId(i, j) < 10 ? " ":""); cout<<'\n';
//     }
}
void checkComponents(){
    for(auto [r, c]: specials){
        int id = cellId(r, c);
        //assert(id <= m*n);
        if(p[id] == id){
            int k = dydis[id];
            int cnt = colCnt[id] - dydis[id];
            if(cnt < 3*k) pos = 0;
            else if(cnt == 3*k) {
                ans += colSum[id];
                //cout<<"sum(eq) of color = "<<id<<": "<<colSum[id]<<'\n';
            }
            else {
                ans += colSum[id] - colMin[id];
               // cout<<"sum(ov) of color = "<<id<<": "<<colSum[id] - colMin[id]<<'\n';
            }
        }
    }
}
/**********************************************************************************
                                 MAIN
**********************************************************************************/
signed main(){
    //_fre();
    turbo();
    readInput(); // also prepares everything
    uniteComps();
    colorTable();
    checkComponents();
    if(!pos) cout<<"No";
    else cout<<ans;
}

Compilation message (stderr)

covering.cpp: In function 'void prepTable()':
covering.cpp:17:33: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); (a)++)
      |                                 ^
covering.cpp:65:5: note: in expansion of macro '_foreq'
   65 |     _foreq(i, 1, n) _foreq(j, 1, m) cin>>table[i][j];
      |     ^~~~~~
covering.cpp:17:33: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   17 | #define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); (a)++)
      |                                 ^
covering.cpp:65:21: note: in expansion of macro '_foreq'
   65 |     _foreq(i, 1, n) _foreq(j, 1, m) cin>>table[i][j];
      |                     ^~~~~~
covering.cpp: In function 'void getSpecialCells()':
covering.cpp:16:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define _for(a, b, c) for(int (a) = (b); (a) < (c); (a)++)
      |                               ^
covering.cpp:69:5: note: in expansion of macro '_for'
   69 |     _for(i, 0, k) {
      |     ^~~~
covering.cpp:73:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |     for(auto [r, c]: specials)
      |              ^
covering.cpp: In function 'void prepDsu()':
covering.cpp:77:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |     for(auto [r, c]: specials)
      |              ^
covering.cpp:17:33: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); (a)++)
      |                                 ^
covering.cpp:79:5: note: in expansion of macro '_foreq'
   79 |     _foreq(i, 1, m*n) dydis[i] = 1;
      |     ^~~~~~
covering.cpp: In function 'void uniteComps()':
covering.cpp:101:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |     for(auto [r, c]: specials)
      |              ^
covering.cpp:16:31: warning: unnecessary parentheses in declaration of 'dir' [-Wparentheses]
   16 | #define _for(a, b, c) for(int (a) = (b); (a) < (c); (a)++)
      |                               ^
covering.cpp:102:9: note: in expansion of macro '_for'
  102 |         _for(dir, 0, 12){
      |         ^~~~
covering.cpp: In function 'void colorTable()':
covering.cpp:114:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  114 |     for(auto [r, c]: specials){
      |              ^
covering.cpp:16:31: warning: unnecessary parentheses in declaration of 'dir' [-Wparentheses]
   16 | #define _for(a, b, c) for(int (a) = (b); (a) < (c); (a)++)
      |                               ^
covering.cpp:117:9: note: in expansion of macro '_for'
  117 |         _for(dir, 0, 4){
      |         ^~~~
covering.cpp:17:33: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); (a)++)
      |                                 ^
covering.cpp:124:6: note: in expansion of macro '_foreq'
  124 |      _foreq(i, 1, n) _foreq(j, 1, m){
      |      ^~~~~~
covering.cpp:17:33: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   17 | #define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); (a)++)
      |                                 ^
covering.cpp:124:22: note: in expansion of macro '_foreq'
  124 |      _foreq(i, 1, n) _foreq(j, 1, m){
      |                      ^~~~~~
covering.cpp: In function 'void checkComponents()':
covering.cpp:148:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  148 |     for(auto [r, c]: specials){
      |              ^

• 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