Submission #336553

#	Time	Username	Problem	Language	Result	Execution time	Memory
336553		Galebickosikasa	Dango Maker (JOI18_dango_maker)	C++17	13 / 100	1 ms	492 KiB

dango_maker

// #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';

	






}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 67