| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 467150 | mtxas | T-Covering (eJOI19_covering) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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){
return n*(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));
_for(dir, 0, 4){
int rr = r + dy[dir], cc = c+dx[dir];
assert(rr <= n+1 && mm <= 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';
// }
}
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;
}