oj.uz

답안 #576308

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
576308 2022-06-13T02:27:56 Z PurpleCrayon Paint (COI20_paint) C++17
48 / 100
 3000 ms 122496 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 2e5+10, MOD = 998244353;
const int B = 400, K = N / B;

#warning change later?
#define hash_map map
#define hash_set set

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

int n, m, p[N], sz[N];
int col[N];
hash_map<int, hash_set<int>> adj_col[N];

int find_set(int v) {
    return v == p[v] ? v : p[v] = find_set(p[v]);
}
set<int> all_big;
void union_sets(int a, int b) { // merge, but only in the dsu
    a = find_set(a), b = find_set(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    p[b] = a, sz[a] += sz[b], sz[b] = 0;
    all_big.erase(b);
}
void union_big(int a, int b) { // just merge adj_col
    a = find_set(a), b = find_set(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    for (auto& [k, v] : adj_col[b]) {
        for (auto& x : v) adj_col[a][k].insert(x);
    }
    adj_col[b].clear();
}
int get_col(int v) {
    return col[find_set(v)];
}

int tt = 0;
int vis[N], use[N];

vector<int> small_adj;
void dfs_small(int v) {
    int i = v / m, j = v % m;
    vis[v] = tt;
    for (int k = 0; k < 4; k++) {
        int ni = i + dx[k], nj = j + dy[k];
        if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
        if (vis[ni*m + nj] == tt) continue;
        if (find_set(ni*m + nj) != find_set(v)) {
            if (use[find_set(ni*m + nj)] != tt) {
                small_adj.push_back(find_set(ni*m + nj));
                use[find_set(ni*m + nj)] = tt;
            }
        } else {
            dfs_small(ni*m + nj);
        }
    }
}
void make_big(int v) { // make information for v to be a big component
    tt++;
    small_adj.clear();
    dfs_small(v);
    all_big.insert(find_set(v));
    for (auto nxt : small_adj) {
        adj_col[find_set(v)][get_col(nxt)].insert(find_set(nxt));
    }
}
void add_small(int v) { // add v to the info of all surrounding big components
    tt++;
    small_adj.clear();
    dfs_small(v);

    for (auto nxt : small_adj) {
        if (sz[find_set(nxt)] >= B) {
            adj_col[find_set(nxt)][get_col(v)].insert(find_set(v));
        }
    }
}
void clear_comp(int v) { // remove v from the info of all surrounding big components
    for (auto nxt : all_big) {
        adj_col[nxt][get_col(v)].erase(find_set(v));
    }
}
void upd_big(int v, int x) {
    v = find_set(v);
    auto to_merge = adj_col[v][x];
    for (auto nxt : to_merge) {
        if (sz[find_set(nxt)] < B) {
            make_big(nxt);
        }
        clear_comp(nxt);
    }
    clear_comp(v);
    for (auto nxt : to_merge) {
        union_big(v, nxt);
        union_sets(v, nxt);
    }
    col[find_set(v)] = x;
    for (auto nxt : all_big) if (adj_col[v][get_col(nxt)].find(nxt) != adj_col[v][get_col(nxt)].end()) {
        adj_col[nxt][get_col(v)].insert(v);
    }
}
void upd_small(int v, int x) {
    tt++;
    small_adj.clear();
    dfs_small(v);

    int new_size = sz[find_set(v)];
    for (auto nxt : small_adj) if (get_col(nxt) == x) {
        new_size += sz[find_set(nxt)];
    }

    if (new_size >= B) {
        make_big(v);
        upd_big(v, x);
    } else {
        clear_comp(v);
        for (auto add : small_adj) {
            if (get_col(add) == x) {
                clear_comp(add);
            }
        }
        for (auto add : small_adj) {
            if (get_col(add) == x) {
                union_sets(v, add);
            }
        }
        col[find_set(v)] = x;
        add_small(v);
    }
}
void upd(int i, int j, int x) {
    int v = i*m + j;
    if (sz[find_set(v)] >= B) upd_big(v, x);
    else upd_small(v, x);
}

int a[N];
void init() { // initially merge stuff
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            p[i*m + j] = i*m + j;
            sz[i*m + j] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i*m + j];
            col[i*m + j] = a[i*m + j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            upd(i, j, a[i*m + j]);
        }
    }
}
void solve() {
    cin >> n >> m;

    init();

    int q; cin >> q;
    while (q--) {
        int i, j, x; cin >> i >> j >> x, --i, --j;
        upd(i, j, x);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cout << col[find_set(i*m + j)] << ' ';
        cout << '\n';
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

Compilation message

paint.cpp:10:2: warning: #warning change later? [-Wcpp]
   10 | #warning change later?
      |  ^~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 14 ms 9940 KB Output is correct
4 Correct 17 ms 9956 KB Output is correct
5 Correct 22 ms 10732 KB Output is correct
6 Correct 111 ms 10060 KB Output is correct
7 Correct 7 ms 9684 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 10896 KB Output is correct
2 Correct 196 ms 12328 KB Output is correct
3 Correct 266 ms 17564 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 658 ms 15148 KB Output is correct
2 Correct 551 ms 15540 KB Output is correct
3 Correct 801 ms 15632 KB Output is correct
4 Correct 310 ms 15572 KB Output is correct
5 Correct 206 ms 15404 KB Output is correct

Subtask #4
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 306 ms 13924 KB Output is correct
2 Correct 760 ms 27336 KB Output is correct
3 Execution timed out 3085 ms 122496 KB Time limit exceeded
4 Halted 0 ms 0 KB -