제출 #331177

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
331177		georgerapeanu	Paint (COI20_paint)	C++11	8 / 100	3094 ms	25576 KiB

paint

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

using namespace std;

const int BUCK = 2e6;
const int DEB = 0;

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

struct node_t{
    int color;
    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));

        vector<int> to_unite = {root};

        if(stuff[root].size() < BUCK){
            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 && c == stuff[neighbor_root].color){
                            to_unite.push_back(neighbor_root);
                        }
                    }
                }
            }
        }
        else{
            for(auto it:stuff[root].neighbors[c]){
                int neighbor_root = find_root(it);
                if(root != neighbor_root && c == stuff[neighbor_root].color){
                    to_unite.push_back(neighbor_root);
                }
            }
        }

        sort(to_unite.begin(),to_unite.end());
        to_unite.resize(unique(to_unite.begin(),to_unite.end()) - to_unite.begin());

        stuff[root].color = c;
        for(auto it:to_unite){
            unite(root,it);
        }

        root = find_root(root);

        if(stuff[root].size() >= BUCK){
            big_roots.push_back(root);
            for(auto &it:big_roots){
                it = find_root(it);
            }
            sort(big_roots.begin(),big_roots.end());
            big_roots.resize(unique(big_roots.begin(),big_roots.end()) - big_roots.begin());
            for(auto it:to_unite){
                if(stuff[it].size() < BUCK){
                    for(auto it2:stuff[it].cells){
                        int x = pos_to_coord(it2).first;
                        int y = pos_to_coord(it2).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){
                                    stuff[root].neighbors[stuff[neighbor_root].color].insert(neighbor_root);
                                }
                            }
                        }
                    }
                    
                }
            }

            for(auto it:big_roots){
                if(it != root && stuff[root].neighbors[stuff[it].color].count(it)){
                    stuff[it].neighbors[c].insert(root);
                }
            }
        }
        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(root != neighbor_root){
                            if(stuff[neighbor_root].size() >= BUCK){
                                stuff[neighbor_root].neighbors[c].insert(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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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