Submission #467151

#TimeUsernameProblemLanguageResultExecution timeMemory
467151mtxasT-Covering (eJOI19_covering)C++14
25 / 100
12 ms6196 KiB
#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 && 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'; // } } 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:64:5: note: in expansion of macro '_foreq'
   64 |     _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:64:21: note: in expansion of macro '_foreq'
   64 |     _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:68:5: note: in expansion of macro '_for'
   68 |     _for(i, 0, k) {
      |     ^~~~
covering.cpp:72:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |     for(auto [r, c]: specials)
      |              ^
covering.cpp: In function 'void prepDsu()':
covering.cpp:76:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |     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:78:5: note: in expansion of macro '_foreq'
   78 |     _foreq(i, 1, m*n) dydis[i] = 1;
      |     ^~~~~~
covering.cpp: In function 'void uniteComps()':
covering.cpp:100:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  100 |     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:101:9: note: in expansion of macro '_for'
  101 |         _for(dir, 0, 12){
      |         ^~~~
covering.cpp: In function 'void colorTable()':
covering.cpp:113:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |     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:115:9: note: in expansion of macro '_for'
  115 |         _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:122:6: note: in expansion of macro '_foreq'
  122 |      _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:122:22: note: in expansion of macro '_foreq'
  122 |      _foreq(i, 1, n) _foreq(j, 1, m){
      |                      ^~~~~~
covering.cpp: In function 'void checkComponents()':
covering.cpp:142:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  142 |     for(auto [r, c]: specials){
      |              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...