제출 #880216

#제출 시각아이디문제언어결과실행 시간메모리
880216niterDango Maker (JOI18_dango_maker)C++14
13 / 100
71 ms216144 KiB
#include <bits/stdc++.h> #define loop(i,a,b) for(int i = (a); i < (b); i ++) #define pb push_back #define ins insert #define pii pair<int,int> #define ff first #define ss second #define op(x) cerr << #x << " = " << x << endl; #define opa(x) cerr << #x << " = " << x << ", "; #define ops(x) cerr << x; #define entr cerr << endl; #define spac cerr << ' '; #define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl; #define ARR(x, nnn) cerr << #x << " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl; #define BAE(x) x.begin(), x.end() #define unilize(x) x.resize(unique(BAE(x)) - x.begin()) #define unisort(x) sort(BAE(x)); unilize(x); using namespace std; typedef long long ll; const int mxn = 3010; char c[mxn][mxn]; vector<pii> EV; const int mxN = (int)(9e6) + 3000; bool vis[mxN], can[mxN]; vector<int> E[mxN]; int p[mxn][mxn]; void dfs(int v, int& sz, bool now, int &black){ sz++; vis[v] = true; if(now) black++; for(auto &u:E[v]){ if(!vis[u]){ dfs(u, sz, !now, black); } } } void check(int x, int y, int ind){ if(p[x][y] == 0){ p[x][y] = ind; } else{ EV.pb({p[x][y], ind}); EV.pb({ind, p[x][y]}); } } int main(){ // freopen("in.txt", "r", stdin); ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; loop(i,0,n){ loop(j,0,m){ cin >> c[i][j]; } } int now = 0; loop(i,0,n){ loop(j,0,m){ if(c[i][j] == 'R' && c[i][j+1] == 'G' && c[i][j+2] == 'W'){ now++; check(i, j, now); check(i, j + 1, now); check(i, j + 2, now); can[now] = true; } if(c[i][j] == 'R' && c[i+1][j] == 'G' && c[i+2][j] == 'W'){ now++; check(i, j, now); check(i + 1, j, now); check(i + 2, j, now); can[now] = true; } } } unisort(EV); for(auto &i:EV){ E[i.ff].pb(i.ss); E[i.ss].pb(i.ff); // opa(i.ff) op(i.ss); } int ans = 0; loop(i,1,mxN){ if((!vis[i]) && can[i]){ int sz = 0, black = 0; dfs(i, sz, 0, black); ans += max(black, sz - black); } } cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...