oj.uz

답안 #1017083

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1017083 2024-07-08T20:28:43 Z CodeAssignment Paint (COI20_paint) C++17
100 / 100
 1768 ms 325016 KB 
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
         
using namespace std;
using namespace __gnu_pbds;
 
/* typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set; */
         
#define el "\n"
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
#define sq(x) (x)*(x)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define sz(x) (int)(x).size()
#define setcontains(set, x) (set.find(x) != set.end())
         
#define umap unordered_map
#define uset unordered_set

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pll> vpll;
         
#define all(x) (x).begin(), (x).end()

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b-1); i >= (a); --i)
#define REP(i, a, b) for (int i = (a); i <= (b); ++i)
#define trav(a, x) for (auto &a : x)
         
struct chash { // large odd number for C
      const uint64_t C = ll(4e18 * acos(0)) | 71;
      ll operator()(ll x) const { return __builtin_bswap64(x * C); }
};
 
template<typename T> using fast_set = __gnu_pbds::gp_hash_table<T, null_type, chash>;
template<typename T, typename H> using fast_set_h = __gnu_pbds::gp_hash_table<T, null_type, H>;
template<typename T, typename U> using fast_map = __gnu_pbds::gp_hash_table<T, U, chash>;
 
#ifdef DEBUG
#include "/home/redkar/kod/cp/lib/debug.cpp"
#else
#define dbg(...)
#define dbgArr(...)
#endif

const ll inf = 1e11;
const ll heavy = 30; // TODO: try 30 

vpll dirs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

ll r, c, q;

ll get_ind(ll R, ll C) {
	if (0 <= R && R < r && 0 <= C && C < c) {
		return R*c + C;
	}
	else return -1;
}

struct UF {
	vll col, parent;
	vector<uset<ll>> edges;
	vector<umap<ll, uset<ll>>> buddy;
	vector<uset<ll>> heavybuddy;
	uset<ll> bigboys;
	
	UF(ll n, vll grid): col(n), parent(n), edges(n), buddy(n), heavybuddy(n) {
		rep(i, 0, n) {
			parent[i] = i;
			col[i] = grid[i];
		}
	}

	ll find(ll x) {
		if (x != parent[x]) parent[x] = find(parent[x]);
		return parent[x];
	}
	void merge(ll a, ll b) {
		a = find(a); b = find(b);
		if (a == b) return;
		//if (mass[a] < mass[b]) swap(a, b);
		//mass[a] += mass[b];
		parent[b] = a;
	}
	void bucket(ll node, ll C) {
		node = find(node);
		col[node] = C;
		ll bst = node;

		uset<ll> compnodes;
		for(auto it = buddy[node][C].begin(); it != buddy[node][C].end();) {
			ll e = find(*it);
			if (col[e] == C) {
				compnodes.insert(*it);
				if (sz(edges[e]) > sz(edges[bst])) {
					bst = e;
				}
				it = next(it);
			}
			else {
				it = buddy[node][C].erase(it);
			}
		}
		buddy[node][C].clear();
		
		trav(edge, heavybuddy[node]) {
			ll e = find(edge);
			if (col[e] == C) {
				compnodes.insert(e);
				if (sz(edges[e]) > sz(edges[bst])) {
					bst = e;
				}
			}
		}
		compnodes.insert(node);
		trav(cur, compnodes) {
			ll cnode = find(cur);
			if (cnode == bst) continue; 
			parent[cnode] = bst;
			trav(edge, edges[cnode]) {
				heavybuddy[edge].erase(cur);	
				heavybuddy[edge].erase(cnode);	
				ll e = find(edge);
				if (setcontains(bigboys, bst)) {
					heavybuddy[e].insert(bst);
				}
				edges[bst].insert(e);
			}
			trav(edge, heavybuddy[cnode]) {
				ll e = find(edge);
				heavybuddy[bst].insert(e);
			}
			trav(edge, buddy[cnode]) {
				trav(nb, edge.S) {
					buddy[bst][edge.F].insert(nb);
				}
			}
		}
		node = find(node);
		if (!setcontains(bigboys, node)) {
			if (sz(edges[node]) > heavy) {
				bigboys.insert(node);
				trav(edge, edges[node]) {
					ll e = find(edge);
					heavybuddy[e].insert(node);
				}
			}
			else {
				trav(edge, edges[node]) {
					ll e = find(edge);
					buddy[e][C].insert(node);
				}
			}
		}
	}
};

void solve() {
	cin >> r >> c;
	//assert(r * c <= 10000);
	vll grid(r*c);
	rep(i, 0, r*c) {
		cin >> grid[i];
	}

	UF uf(r*c, grid);

	//dbg(1);
	dbg(1);
	rep(phase, 0, 2) {
		dbg(phase);
		rep(i, 0, r) rep(j, 0, c) {
			ll cell = get_ind(i, j);
			ll cell_leader = uf.find(cell);
			//ll cell_color = uf.col[uf.find(cell)];
			trav(d, dirs) {
				ll y = i + d.F, x = j + d.S;		
				if (y < 0 || y >= r || x < 0 || x >= c) continue;
				ll nb_cell = get_ind(y, x);
				ll nb_leader = uf.find(nb_cell);

				if (grid[cell] == grid[nb_cell] && phase == 0) {
					uf.merge(cell, nb_cell);
				}
				else if (grid[cell] != grid[nb_cell] && phase == 1) {
					uf.buddy[cell_leader][uf.col[nb_leader]].insert(nb_leader);
					uf.buddy[nb_leader][uf.col[cell_leader]].insert(cell_leader);
					uf.edges[cell_leader].insert(nb_leader);
					uf.edges[nb_leader].insert(cell_leader);
				}
			}
		}
	}
	//dbg(uf.col);
	//dbg(uf.buddy);
	dbg(2);
	//uf.reorganize();
	dbg(3);
	//dbg(uf.col);
	//dbg(uf.buddy);

	cin >> q;
	while(q--) {
		dbg(q);
		ll y, x, C;
		cin >> y >> x >> C; y--, x--;
		
		//dbg(y, x, C);
		ll cur = uf.find(get_ind(y, x));

		if (uf.col[cur] != C) {
			uf.bucket(cur, C);
		}
		/*
		rep(i, 0, r) {
			cerr << "temp: ";
			rep(j, 0, c) {
				cerr << uf.col[uf.find(get_ind(i, j))] << " ";
			}
			cerr << el;
		}
		*/
	}

	rep(i, 0, r) {
		rep(j, 0, c) {
			cout << uf.col[uf.find(get_ind(i, j))] << " ";
		}
		cout << el;
	}
}

int main() { 
	faster
        int test = 1; // cin >> test;
	REP(tc, 1, test) {
		solve();
	}
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1372 KB Output is correct
2 Correct 3 ms 1372 KB Output is correct
3 Correct 26 ms 18380 KB Output is correct
4 Correct 36 ms 16732 KB Output is correct
5 Correct 25 ms 10584 KB Output is correct
6 Correct 20 ms 9048 KB Output is correct
7 Correct 1 ms 344 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 78280 KB Output is correct
2 Correct 236 ms 75824 KB Output is correct
3 Correct 366 ms 141732 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 743 ms 202432 KB Output is correct
2 Correct 660 ms 194360 KB Output is correct
3 Correct 719 ms 201032 KB Output is correct
4 Correct 942 ms 194340 KB Output is correct
5 Correct 761 ms 180112 KB Output is correct

Subtask #4
52.0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 961 ms 223856 KB Output is correct
2 Correct 804 ms 193600 KB Output is correct
3 Correct 1224 ms 230540 KB Output is correct
4 Correct 1316 ms 245220 KB Output is correct
5 Correct 1768 ms 325016 KB Output is correct
6 Correct 523 ms 188908 KB Output is correct
7 Correct 511 ms 150076 KB Output is correct
8 Correct 339 ms 122324 KB Output is correct
9 Correct 1447 ms 275592 KB Output is correct