제출 #857740

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
857740		Denjell	Paint (COI20_paint)	C++14	48 / 100	3035 ms	64088 KiB

paint

#include <bits/stdc++.h>
#include <random>
#include <ctime>
using namespace std;

typedef int64_t ll;
template<typename T>             istream& operator>>(istream& is, vector<T>& v) { for (auto& i : v) is >> i;        return is; }
template<typename T>             ostream& operator<<(ostream& os, const vector<T>& v) { for (auto& i : v) os << i << "\n"; return os; }
template<typename T>             istream& operator>>(istream& is, pair<T, T>& v) { is >> v.first >> v.second;        return is; }
template<typename T>             ostream& operator<<(ostream& os, const pair<T, T>& v) { os << v.first << " " << v.second; return os; }
#define MOD 1000000007
//#define MOD 998244353
uint64_t gcd(uint64_t a, uint64_t b) {
	uint64_t r;
	while (b != 0) {
		r = a % b;
		a = b;
		b = r;
	}
	return a;

}
uint64_t mypow(uint64_t base, uint64_t exp) {
	uint64_t result = 1;
	while (exp > 0) {
		if (exp & 1) result = (result * base);
		base = (base * base);
		exp >>= 1;
	}
	return result;
}
uint64_t modpow(uint64_t base, uint64_t exp, uint64_t modulus) {
	base %= modulus;
	uint64_t result = 1;
	while (exp > 0) {
		if (exp & 1) result = (result * base) % modulus;
		base = (base * base) % modulus;
		exp >>= 1;
	}
	return result;
}
inline int log2(uint64_t n) {
	unsigned int r = 0;
	while (n >>= 1) r++;
	return r;
}
int64_t egcd(int64_t a, int64_t b, int64_t& x, int64_t& y) {
	x = 1, y = 0;
	int x1 = 0, y1 = 1, a1 = a, b1 = b;
	while (b1) {
		int q = a1 / b1;
		tie(x, x1) = make_tuple(x1, x - q * x1);
		tie(y, y1) = make_tuple(y1, y - q * y1);
		tie(a1, b1) = make_tuple(b1, a1 - q * b1);
	}
	return a1;
}

inline uint64_t modinv(uint64_t x, uint64_t mod) {
	return modpow(x, mod - 2, mod);
}

void precomp() {

}

struct DSU {
	DSU(int parent = -1) : parent(parent), color(-1) {}
	int parent;
	int color;
	set<int> neighbours;
};

void init(vector<DSU>& a) {
	for (int i = 0; i < a.size(); i++) a[i].parent = i;
}

int find_set(vector<DSU>& a, int v) {
	if (v == a[v].parent) return v;
	return a[v].parent = find_set(a, a[v].parent);
}

void union_sets(vector<DSU>& a, int u, int v) {
	u = find_set(a, u);
	v = find_set(a, v);
	if (u != v) {
		if (a[u].neighbours.size() < a[v].neighbours.size()) swap(u, v);
		a[v].parent = u;
		a[u].neighbours.insert(a[v].neighbours.begin(), a[v].neighbours.end());
	}
}

int dx[] = { 1, 0, -1,  0 };
int dy[] = { 0, 1,  0, -1 };

void solve() {
	ll n, m; 
	cin >> n >> m;
	vector<vector<int>> a(n, vector<int>(m));
	cin >> a;
	auto p = [m](int r, int c) {
		return r * m + c;
	};
	auto valid = [n, m](int r, int c) {
		return r >= 0 && r < n && c >= 0 && c < m;
	};
	vector<DSU> b(n * m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			b[p(i, j)].color = a[i][j];
			b[p(i, j)].parent = p(i,j);
			for (int k = 0; k < 4; k++) {
				auto nx = i + dx[k];
				auto ny = j + dy[k];
				if (!valid(nx, ny)) continue;
				b[p(i, j)].neighbours.insert(p(nx, ny));
			}

		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < 2; k++) { // 2 since only look right and down
				auto nx = i + dx[k];
				auto ny = j + dy[k];
				if (!valid(nx, ny)) continue;
				auto pold = find_set(b, p(i, j));
				auto pnew = find_set(b, p(nx, ny));
				if (b[pold].color == b[pnew].color) {
					union_sets(b, pold, pnew);
				}
			}
		}
	}

	ll q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		ll x, y, c;
		cin >> x >> y >> c;
		x--; y--;
		auto pos = find_set(b, p(x, y));
		b[pos].color = c;
		vector<int> tomerge;
		for (auto it = b[pos].neighbours.begin(); it != b[pos].neighbours.end();) {
			auto pnew = find_set(b, *it);
			if (pos == pnew) {
				it = b[pos].neighbours.erase(it);
			} 
			else {
				if (b[pos].color == b[pnew].color) {
					tomerge.push_back(pnew);
				}
				it++;
			}
		}
		for (auto e : tomerge) {
			auto pos = find_set(b, p(x, y));
			union_sets(b, e, pos);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			auto pos = find_set(b, p(i, j));
			cout << b[pos].color << " ";
		}
		cout << "\n";
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	precomp();
	int t = 1;
	//cin >> t;
	while (t--) {
		solve();
	}

	return 0;

}

컴파일 시 표준 에러 (stderr) 메시지

paint.cpp: In function 'void init(std::vector<DSU>&)':
paint.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<DSU>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for (int i = 0; i < a.size(); i++) a[i].parent = i;
      |                  ~~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 31 / 31
• Subtask 4: 0 / 52