Submission #331158

#	Time	Username	Problem	Language	Result	Execution time	Memory
331158		georgerapeanu	Paint (COI20_paint)	C++11	0 / 100	260 ms	25580 KiB

paint

#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>

using namespace std;

const int BUCK = 400;
const int DEB = 0;

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

struct node_t{
    int color;
    bool initialized;
    vector<int> cells;
    unordered_map<int,unordered_set<int> > neighbors;

    void merge(const node_t &other){
        for(auto it:other.cells){
            this->cells.push_back(it);
        }
        for(auto it:other.neighbors){
            for(auto it2:it.second){
                this->neighbors[it.first].insert(it2);
            }
        }
    }

    int size(){
        return (int)cells.size();
    }
};

class DSU{
    int n,m;
    vector<int> father;
    vector<node_t> stuff;
    vector<int> big_roots;

    int coord_to_pos(int x,int y){
        return (x - 1) * m + y;
    }

    pair<int,int> pos_to_coord(int pos){
        return {(pos - 1) / m + 1,(pos - 1) % m + 1};
    }
    
    int find_root(int nod){
        if(father[nod] == 0){
            return nod;
        }
        return father[nod] = find_root(father[nod]);
    }

    bool unite(int x,int y){
        x = find_root(x);
        y = find_root(y);

        if(x == y){
            return false;
        }

        if(stuff[x].size() > stuff[y].size()){
            swap(x,y);
        }

        father[x] = y;

        stuff[y].merge(stuff[x]);

        return true;
    }

public:

    DSU(int n,int m){
        this->n = n;
        this->m = m;
        father = vector<int>(n * m + 1,0);
        stuff = vector<node_t>(n * m + 1);
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                stuff[coord_to_pos(i,j)].cells = {coord_to_pos(i,j)};
                stuff[coord_to_pos(i,j)].color = -1;
            }
        }

    }

    void update_color(int x,int y,int c){
        int root = find_root(coord_to_pos(x,y));
        if(DEB){
            printf("root %d\n",root);
        }
        int initial_size = stuff[root].size();
        vector<int> to_unite;
        if(stuff[root].size() >= BUCK && stuff[root].initialized == true){
            for(auto it:stuff[root].neighbors[c]){
                int neighbor_root = find_root(it);
                if(DEB){
                    printf("deb %d %d %d\n",root,neighbor_root,stuff[neighbor_root].color);
                }
                if(stuff[neighbor_root].color == c){
                    to_unite.push_back(neighbor_root);
                }
            }
            stuff[root].neighbors[c].clear();
        }
        else{
            for(auto it:stuff[root].cells){
                int x = pos_to_coord(it).first;
                int y = pos_to_coord(it).second;
                for(int k = 0;k < 4;k++){
                    int xx = x + dx[k];
                    int yy = y + dy[k];
                    if(1 <= xx && xx <= n && 1 <= yy && yy <= m){
                        int neighbor_root = find_root(coord_to_pos(xx,yy));
                        if(DEB){
                            printf("deb %d %d %d\n",root,neighbor_root,stuff[neighbor_root].color);
                        }
                        if(stuff[neighbor_root].color == c){
                            to_unite.push_back(neighbor_root);
                        }
                    }
                }
            }
        }
        for(auto it:to_unite){
            if(DEB){
                printf("unite %d %d\n",root,it);
            }
            unite(root,it);
        }
        root = find_root(coord_to_pos(x,y));
        stuff[root].color = c;
        if(initial_size < BUCK || stuff[root].initialized == false){
            stuff[root].initialized = true;
            if(stuff[root].size() >= BUCK){
                big_roots.push_back(root);
            }
            for(auto it:stuff[root].cells){
                int x = pos_to_coord(it).first;
                int y = pos_to_coord(it).second;
                for(int k = 0;k < 4;k++){
                    int xx = x + dx[k];
                    int yy = y + dy[k];
                    if(1 <= xx && xx <= n && 1 <= yy && yy <= m){
                        int neighbor_root = find_root(coord_to_pos(xx,yy));
                        if(root != neighbor_root){
                            if(stuff[neighbor_root].size() >= BUCK && stuff[neighbor_root].initialized == true){
                                stuff[neighbor_root].neighbors[c].insert(root);
                            }
                            if(stuff[root].size() >= BUCK){
                                stuff[root].neighbors[stuff[neighbor_root].color].insert(neighbor_root);
                            }
                        }
                    }
                }
            }
        }
        else{
            for(auto it:to_unite){
                if(stuff[it].size() < BUCK){
                    int root = it;
                    for(auto it:stuff[root].cells){
                        int x = pos_to_coord(it).first;
                        int y = pos_to_coord(it).second;
                        for(int k = 0;k < 4;k++){
                            int xx = x + dx[k];
                            int yy = y + dy[k];
                            if(1 <= xx && xx <= n && 1 <= yy && yy <= m){
                                int neighbor_root = find_root(coord_to_pos(xx,yy));
                                if(root != neighbor_root){
                                    if(stuff[neighbor_root].size() >= BUCK && stuff[neighbor_root].initialized == true){
                                        stuff[neighbor_root].neighbors[c].insert(root);
                                    }
                                    if(stuff[root].size() >= BUCK){
                                        stuff[root].neighbors[stuff[neighbor_root].color].insert(neighbor_root);
                                    }
                                }
                            }
                        }
    
                    } 
                }
            }
            for(auto &it:big_roots){
                it = find_root(it);
                if(it != root && stuff[root].neighbors[stuff[it].color].count(it)){
                    stuff[it].neighbors[c].insert(root);
                }
            }
        }
        if(DEB){
            printf("end root %d\n\n",root);
        }
    }

    int get_color(int x,int y){
        return stuff[find_root(coord_to_pos(x,y))].color;
    }

    void print(){
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
//                printf("%d ",find_root(coord_to_pos(i,j)));
                printf("%d ",get_color(i,j));
            }
            printf("\n");
        }
    }
};


int main(){

    int n,m;
    scanf("%d %d",&n,&m);

    DSU solver(n,m);
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            int c;
            scanf("%d",&c);
            solver.update_color(i,j,c);
        }
    }
    if(DEB){
        solver.print();
    }

    /*for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            solver.update_color(i,j,solver.get_color(i,j));
        }
    }*/

    int q;

    scanf("%d",&q);

    while(q--){
        int x,y,c;
        scanf("%d %d %d",&x,&y,&c);
        solver.update_color(x,y,c);
        if(DEB){
            solver.print();
        }
    }

    solver.print();

    return 0;
}

Compilation message (stderr)

paint.cpp: In function 'int main()':
paint.cpp:223:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  223 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
paint.cpp:229:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  229 |             scanf("%d",&c);
      |             ~~~~~^~~~~~~~~
paint.cpp:245:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  245 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
paint.cpp:249:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  249 |         scanf("%d %d %d",&x,&y,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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