oj.uz

Submission #853318

# Submission time Handle Problem Language Result Execution time Memory
853318 2023-09-24T05:41:06 Z lto5 Paint (COI20_paint) C++17
8 / 100
 3000 ms 22056 KB 
#include <bits/stdc++.h>
using namespace std;

const int dx[] = { -1, 0, 0, 1 }, dy[] = { 0, -1, 1, 0 };
const int N = 1005;
const int N2 = 200005;

int m, n;
int a[N2];
int q;
pair<int, int> org[N2];

bool in_grid(int u, int v) { return u >= 1 && u <= m && v >= 1 && v <= n; }
#define id(x, y) (((x)-1) * n + (y))
int get_type(char ch) { return ch == 'B'; }

void read() {
    cin >> m >> n;

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) cin >> a[id(i, j)];
}

int id_comp[N2];
bool done[N2];
int type[N2];
int area[N2];
vector<int> adj[N2];
int num_comp;

void dfs(int u, int v, int val) {
    if (!in_grid(u, v))
        return;
    if (id_comp[id(u, v)])
        return;
    if (a[id(u, v)] != val)
        return;

    id_comp[id(u, v)] = num_comp;
    area[num_comp]++;

    for (int i = 0; i < 4; i++) {
        dfs(u + dx[i], v + dy[i], val);
    }
}

void pre_comp() {
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (!id_comp[id(i, j)]) {
                num_comp++;
                type[num_comp] = a[id(i,j)];//get_type(a[id(i, j)]);
                dfs(i, j, a[id(i, j)]);
            }

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 0; k < 2; k++) {
                int new_u = i + dx[k];
                int new_v = j + dy[k];

                if (!in_grid(new_u, new_v))
                    continue;

                if (id_comp[id(i, j)] != id_comp[id(new_u, new_v)])
                    adj[id_comp[id(i, j)]].emplace_back(id_comp[id(new_u, new_v)]),
                        adj[id_comp[id(new_u, new_v)]].emplace_back(id_comp[id(i, j)]);
            }
}

int par[N2];
int max_size;
int cnt;

int root(int u) {
    if (par[u] < 0)
        return u;
    return par[u] = root(par[u]);
}

bool join(int u, int v) {
    int old_u = u, old_v = v;

    u = root(u);
    v = root(v);

    if (type[u] != type[v])
        return false;

    if (u == v) {
        return false;
    }
    if (par[u] > par[v])
        swap(u, v);
        
    vector<int> wait;

    for (int& x : adj[v])
        if (root(x) == u)
            continue;
        else {
            adj[u].push_back(root(x));
            //wait.emplace_back(root(x));
        }

    adj[v].clear();
    
    //for (int x:wait) adj[x].emplace_back(u);
    //adj[v]=wait;

    area[u] += area[v];
    par[u] += par[v];
    par[v] = u;

    max_size = max(max_size, area[u]);
    cnt--;

    return true;
}

void solve() {
    cnt = num_comp;
    for (int i = 1; i <= cnt; i++) {
        max_size = max(max_size, area[i]);
    }

    memset(par, -1, sizeof(par));

    cin >> q;

    while (q--) {
        int t;//char c;
        int i, j;

        cin >> i>>j>>t;

        //int t = get_type(c);
        int u = root(id_comp[id(i, j)]);

        if (t != type[u]) {
            type[u] = t;//cerr<<"fill "<<u<<" with "<<t<<endl;
            vector<int> old_adj_u = adj[u];
            //adj[u].clear();

            for (int& v : old_adj_u) {
                if (root(v) == u)
                    continue;
                join(u, v);
            }
        }

        //cout << cnt << " " << max_size << "\n";
    }
    
    for (int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++){
            cout<<type[root(id_comp[id(i,j)])]<<" \n"[j==n];
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    //  freopen("input.txt", "r", stdin);
    //  freopen("output.txt", "w", stdout);

    read();
    pre_comp();
    solve();

    return 0;
}

Compilation message

paint.cpp: In function 'bool join(int, int)':
paint.cpp:82:9: warning: unused variable 'old_u' [-Wunused-variable]
   82 |     int old_u = u, old_v = v;
      |         ^~~~~
paint.cpp:82:20: warning: unused variable 'old_v' [-Wunused-variable]
   82 |     int old_u = u, old_v = v;
      |                    ^~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 2 ms 6744 KB Output is correct
3 Correct 6 ms 7256 KB Output is correct
4 Correct 6 ms 7260 KB Output is correct
5 Correct 148 ms 7312 KB Output is correct
6 Correct 57 ms 7268 KB Output is correct
7 Correct 1 ms 6744 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 8796 KB Output is correct
2 Correct 64 ms 12628 KB Output is correct
3 Execution timed out 3054 ms 20552 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 20456 KB Output is correct
2 Correct 136 ms 19640 KB Output is correct
3 Correct 155 ms 21928 KB Output is correct
4 Correct 1544 ms 22056 KB Output is correct
5 Execution timed out 3034 ms 19840 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 14580 KB Output is correct
2 Execution timed out 3035 ms 17288 KB Time limit exceeded
3 Halted 0 ms 0 KB -