제출 #336553

#제출 시각아이디문제언어결과실행 시간메모리
336553GalebickosikasaDango Maker (JOI18_dango_maker)C++17
13 / 100
1 ms492 KiB
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx") // #pragma comment(linker, "/stack:200000000"] #include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <unordered_set> #include <unordered_map> #include <set> #include <map> #include <queue> #include <deque> #include <bitset> #include <stack> #include <random> #include <fstream> #include <sstream> #include <chrono> #define fi first #define se second #define pb push_back #define ll long long #define ld long double #define hm unordered_map #define pii pair<int, int> #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define cinv(v) for (auto& x: v) cin >> x #define fr(i, n) for (int i = 0; i < n; ++i) #define fl(i, l, n) for (int i = l; i < n; ++i) #define int ll template <typename T1, typename T2> inline bool chkmin(T1 &x, const T2 &y) {if (x > y) {x = y; return 1;} return 0;} template <typename T1, typename T2> inline bool chkmax(T1 &x, const T2 &y) {if (x < y) {x = y; return 1;} return 0;} using namespace std; #ifdef LOCAL #define dbg(x) cerr << #x << " : " << x << '\n' const int maxn = 20; #else #define dbg(x) const int maxn = 2e5 + 20; #endif //tg: @galebickosikasa ostream& operator << (ostream& out, const pii& v) { out << v.fi << ", " << v.se; return out; } template<typename T> ostream& operator << (ostream& out, const vector<T>& v) { for (auto& x: v) out << x << " "; return out; } istream& operator >> (istream& in, pii& a) { in >> a.fi >> a.se; return in; } const ll inf = (ll) 2e9; const ld pi = asin (1) * 2; const ld eps = 1e-8; const ll mod = (ll)1e9 + 7; const ll ns = 97; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); struct DSU { vector<int> a, b, t; DSU (int n) { a = b = t = vector<int> (n); for (int i = 0; i < n; ++i) t[i] = i; } int get (int x) { if (t[x] == x) return x; return t[x] = get (t[x]); } void join (int x, int y) { x = get (x), y = get (y); if (x != y) { t[x] = y; a[y] += a[x]; b[y] += b[x]; } } }; char goo[3000][3000]; int a[3000][3000], b[3000][3000]; signed main () { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, m; cin >> n >> m; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) cin >> goo[i][j]; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) a[i][j] = -1; int c = 0; for (int i = 2; i < n; ++i) for (int j = 0; j < m; ++j) if (goo[i - 2][j] == 'R' && goo[i - 1][j] == 'G' && goo[i][j] == 'W') a[i - 2][j] = a[i - 1][j] = a[i][j] = c++; int last = c; for (int i = 0; i < n; ++i) for (int j = 2; j < m; ++j) if (goo[i][j - 2] == 'R' && goo[i][j - 1] == 'G' && goo[i][j] == 'W') b[i][j - 2] = b[i][j - 1] = b[i][j] = c++; DSU dsu (c); for (int i = 0; i < last; ++i) dsu.a[i] = 1; for (int i = last; i < c; ++i) dsu.b[i] = 1; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { if (a[i][j] != -1 && b[i][j] != -1) dsu.join (a[i][j], b[i][j]); } set <pii> ans; for (int i = 0; i < c; ++i) { int x = dsu.get (i); ans.insert ({x, max (dsu.a[x], dsu.b[x])}); } int res = 0; for (auto& x: ans) res += x.se; cout << res << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...