Submission #1043780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043780		fryingduc	Paint (COI20_paint)	C++17	100 / 100	1040 ms	41248 KiB

paint

#include "bits/stdc++.h"
using namespace std;

const int maxn = 2e5 + 5;
const int C = 1e5 + 5;
const int B = 300;

int n, m, q;
vector<vector<int>> a, id, vis;
const int movex[] = {1, -1, 0, 0};
const int movey[] = {0, 0, 1, -1};

int total;

bool flip;

vector<int> g[maxn];

int color[maxn];
map<int, vector<int>> mp[maxn];

struct dsu {
    int n;
    vector<int> par, sz;
    dsu() {}
    dsu(int n) : n(n), par(n + 5), sz(n + 5) {
        for(int i = 0; i <= n; ++i) {
            par[i] = i;
            sz[i] = 1;
            color[i] = -1;
        }
    }
    int find(int u) {
        return u == par[u] ? u : par[u] = find(par[u]);
    }
    void join(int u, int v) {
        u = find(u), v = find(v);
        
        if(u == v) return;
        if(sz[u] < sz[v]) swap(u, v);
        
        
        for(auto it:mp[v]) {
            for(auto i:it.second) {
                mp[u][it.first].push_back(i);
            }
        }
        mp[v].clear();  
        par[v] = u;
        
        if(sz[u] > B) {
            for(auto i:g[v]) {
                i = find(i);
                if(i == u) continue;
                
                if(sz[i] > B) {
                    g[u].push_back(i);
                    if(sz[v] <= B)
                        g[i].push_back(u);
                }
                else {
                    mp[u][color[i]].push_back(i);   
                }
            }
        }
        else if(sz[u] + sz[v] > B) {
            vector<int> adj;
            int cur_ver = u;
            for(int ite = 0; ite < 2; ++ite) {
                for(auto i:g[cur_ver]) {
                    i = find(i);
                    if(i == u) continue;
                    if(sz[i] > B) {
                        adj.push_back(i);
                        g[i].push_back(u);
                    }
                    else {
                        mp[u][color[i]].push_back(i);
                    }
                }
                cur_ver = v;
            }
            
            g[u] = adj;
        }
        else {
            for(auto i:g[v]) {
                i = find(i);
                g[u].push_back(i);
            }
            for(auto i:g[u]) {
                i = find(i);
                if(sz[i] > B) mp[i][color[u]].push_back(u);
            }
        }
        sz[u] += sz[v];
        g[v].clear();
    }
    bool is_joined(int u, int v) {
        return find(u) == find(v);
    }
} d;
void undo_small(int x, int y, int c) {
    queue<pair<int, int>> q;
    q.push({x, y});
    vis[x][y] = 0;
    color[d.find(id[x][y])] = c;
    while(!q.empty()) {
        int u = q.front().first, v = q.front().second;
        q.pop();
        for(int move = 0; move < 4; ++move) {
            int i = movex[move] + u, j = movey[move] + v;
            
            if(i > n || j > m || i < 1 || j < 1 || !vis[i][j]) continue;
            if(vis[i][j]) {
                vis[i][j] = 0;
                q.push({i, j});
            }
        }
    }
}
void color_small(int x, int y, int c) {
    queue<pair<int, int>> q;
    q.push({x, y});
    vis[x][y] = 1;
    color[d.find(id[x][y])] = c;
    while(!q.empty()) {
        int u = q.front().first, v = q.front().second;
        q.pop();
        for(int move = 0; move < 4; ++move) {
            int i = movex[move] + u, j = movey[move] + v;
            
            if(i > n || j > m || i < 1 || j < 1 || vis[i][j]) continue;
            if(d.find(id[i][j]) == d.find(id[x][y])) {
                vis[i][j] = 1;
                q.push({i, j});
            }
            else if(color[d.find(id[i][j])] == c) {
                d.join(id[x][y], id[u][v]);
            }
        }
    }
    undo_small(x, y, c);
}
void add_edge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}
void query(int u, int c) {
    
    vector<int> adjj;
    u = d.find(u);
    color[u] = c;
    for(auto v:g[u]) {
        v = d.find(v);
        if(color[v] == color[u]) {
            adjj.push_back(v);
        }
    }
    if(mp[u].find(c) != mp[u].end()) {
        vector<int> &now = mp[u][c];
        for(auto v:now) {
            v = d.find(v);
            if(color[v] == color[u]) {
                adjj.push_back(v);
            }
        }
        
        mp[u].erase(c);
    }
    
    for(auto v:adjj) {
        d.join(u, v);
    }
    
    u = d.find(u);
    if(d.sz[u] <= B) {
        for(auto v:g[u]) {
            v = d.find(v);
            if(d.sz[v] > B) {
                mp[v][color[u]].push_back(u);
            }
        }
    }    
}
void solve() {
    cin >> n >> m;
    a.resize(n + 5, vector<int>(m + 5));
    id.resize(n + 5, vector<int>(m + 5));
    vis.resize(n + 5, vector<int>(m + 5));
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            cin >> a[i][j];
            id[i][j] = ++total;
        }
    } 
    d = dsu(total + 5);
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(i < n) {
                add_edge(id[i][j], id[i + 1][j]);
            }
            if(j < m) {
                add_edge(id[i][j], id[i][j + 1]);
            }
        }
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            query(id[i][j], a[i][j]);
        }
    }
    cin >> q;
    while(q--) {
        int x, y, c; cin >> x >> y >> c;
        query(id[x][y], c);
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            cout << color[d.find(id[i][j])] << ' ';
        }
        cout << '\n';
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    #define task "paint"
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    
    solve();
    return 0;
}
/*
4 4
1 0 1 3
1 3 2 2
3 3 1 2
2 2 1 3
3
1 2 3
3 2 1
4 2 3

6 6
1 2 1 2 2 2
3 1 2 1 3 1
3 3 2 3 2 2
2 3 1 3 3 2
3 3 3 3 3 3
2 3 2 2 2 1 
4 
6 2 2
3 5 2
3 2 3
1 2 3

6 6
1 2 1 2 2 2
3 1 2 1 3 1
3 3 2 3 2 2
2 3 1 3 3 2
3 3 3 3 3 3
2 3 2 2 2 1 
2
6 2 2
6 2 3



4 2 
0 0 
1 1 
0 0 
3 3 
3
2 1 0
1 1 5
4 1 7 

3 2 
0 0 
1 1 
0 0 
1
2 1 0

2 3 
0 0 0 
1 1 1
2
2 1 0
1 1 5

*/

Compilation message (stderr)

paint.cpp: In function 'int main()':
paint.cpp:231:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  231 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
paint.cpp:232:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  232 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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