#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, deg, mass;
vector<map<ll, set<ll>>> buddy;
vector<uset<ll>> heavybuddy;
uset<ll> bigboys;
UF(ll n, vll grid): col(n), parent(n), deg(n), mass(n), buddy(n), heavybuddy(n) {
rep(i, 0, n) {
parent[i] = i;
col[i] = grid[i];
mass[i] = 1;
}
}
ll find(ll x) {
if (x != parent[x]) parent[x] = find(parent[x]);
return parent[x];
}
void reorganize() {
// reorganize into heavy and not heavy
rep(i, 0, r) rep(j, 0, c) {
ll component = find(get_ind(i, j));
if (mass[component] >= heavy) {
bigboys.insert(component);
trav(COL, buddy[component]) {
trav(nb, COL.S) {
// TODO: what about adding the other way? Edit: I am not sure what I meant here
assert(setcontains(buddy[nb][col[component]], component) || setcontains(heavybuddy[nb], component));
buddy[nb][col[component]].erase(component);
heavybuddy[nb].insert(component);
}
}
trav(nb, heavybuddy[component]) {
buddy[nb][col[component]].erase(component); /* hopefully this doesnt cause runtime error */
heavybuddy[nb].insert(component);
}
}
}
}
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) {
ll oldColor = col[node];
col[node] = C;
if (!deg[node]) return;
ll mx = 0;
ll bst = -1;
trav(nb, buddy[node][C]) { // light neighbors (TODO: is this even necessary)
assert(col[nb] == C);
assert(col[find(nb)] == C);
if (deg[nb] > mx) {
mx = deg[nb];
bst = nb;
}
}
trav(nb, heavybuddy[node]) { // heavy neighbors;
if (col[nb] == C && deg[nb] > mx) {
mx = deg[nb];
bst = nb;
}
}
if (bst == -1) {
if (!setcontains(bigboys, node)) {
trav(nb, heavybuddy[node]) {
assert(col[nb] != C); // cause otherwise bst should not be -1
buddy[nb][oldColor].erase(node);
buddy[nb][C].insert(node);
}
trav(COL, buddy[node]) {
trav(nb, COL.S) {
assert(col[nb] != C); // cause otherwise bst should not be -1
buddy[nb][oldColor].erase(node);
buddy[nb][C].insert(node);
}
}
}
return;
}
assert(bst != -1); // make sure we actually found a largest, since deg[node] > 0
//
parent[node] = bst; // TODO?: I think this is where you do this? Or maybe it doesn't really matter where
if (setcontains(bigboys, node)) {
heavybuddy[bst].erase(node);
}
else buddy[bst][oldColor].erase(node);
trav(COL, buddy[node]) {
if (COL.F == C) continue;
trav(nb, COL.S) {
buddy[nb][oldColor].erase(node);
if (setcontains(bigboys, bst)) heavybuddy[nb].insert(bst);
else buddy[nb][C].insert(bst);
buddy[bst][col[nb]].insert(nb);
}
}
trav(nb, heavybuddy[node]) {
if (col[nb] == C) continue;
buddy[nb][oldColor].erase(node);
if (setcontains(bigboys, bst)) heavybuddy[nb].insert(bst);
else buddy[nb][C].insert(bst);
heavybuddy[bst].insert(nb);
}
trav(nb, buddy[node][C]) {
if (nb == bst) continue;
parent[nb] = bst;
assert(!setcontains(bigboys, nb)); // shouldnt be heavy in buddy[node][C]
trav(nb2, heavybuddy[nb]) {
if (nb2 == node) continue;
buddy[nb2][C].erase(nb);
if (setcontains(bigboys, bst)) heavybuddy[nb2].insert(bst);
else buddy[nb2][C].insert(bst);
heavybuddy[bst].insert(nb2);
}
trav(COL, buddy[nb]) {
trav(nb2, COL.S) {
if (nb2 == node) continue;
buddy[nb2][C].erase(nb);
if (setcontains(bigboys, bst)) heavybuddy[nb2].insert(bst);
else buddy[nb2][C].insert(bst);
buddy[bst][col[nb2]].insert(nb2);
}
}
heavybuddy[nb].clear();
buddy[nb].clear();
}
trav(nb, heavybuddy[node]) {
if (col[nb] != C || nb == bst) continue;
parent[nb] = bst;
trav(nb2, heavybuddy[nb]) {
if (nb2 == node) continue;
heavybuddy[nb2].erase(nb);
if (setcontains(bigboys, bst)) heavybuddy[nb2].insert(bst);
else buddy[nb2][C].insert(bst);
heavybuddy[bst].insert(nb2);
}
trav(COL, buddy[nb]) {
trav(nb2, COL.S) {
if (nb2 == node) continue;
heavybuddy[nb2].erase(nb);
if (setcontains(bigboys, bst)) heavybuddy[nb2].insert(bst);
else buddy[nb2][C].insert(bst);
buddy[bst][col[nb2]].insert(nb2);
}
}
heavybuddy[nb].clear();
buddy[nb].clear();
}
buddy[node].clear();
heavybuddy[node].clear();
}
};
void solve() {
cin >> r >> c;
vll grid(r*c);
rep(i, 0, r*c) {
cin >> grid[i];
}
UF uf(r*c, grid);
rep(phase, 0, 2) {
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.deg[cell_leader]++;
uf.deg[nb_leader]++;
}
}
}
}
uf.reorganize();
cin >> q;
while(q--) {
ll y, x, C;
cin >> y >> x >> C; y--, x--;
ll cur = uf.find(get_ind(y, x));
if (uf.col[cur] != C) {
uf.bucket(cur, C);
}
}
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();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
856 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 3 |
Correct |
15 ms |
9540 KB |
Output is correct |
| 4 |
Correct |
22 ms |
6232 KB |
Output is correct |
| 5 |
Execution timed out |
3091 ms |
148484 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
27892 KB |
Output is correct |
| 2 |
Correct |
79 ms |
31556 KB |
Output is correct |
| 3 |
Correct |
135 ms |
62744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
183 ms |
84532 KB |
Output is correct |
| 2 |
Correct |
186 ms |
84524 KB |
Output is correct |
| 3 |
Correct |
201 ms |
83620 KB |
Output is correct |
| 4 |
Correct |
220 ms |
81388 KB |
Output is correct |
| 5 |
Correct |
162 ms |
77456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
509 ms |
89308 KB |
Output is correct |
| 2 |
Execution timed out |
3068 ms |
92776 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
