結果

問題 No.307 最近色塗る問題多くない？
ユーザー imulanimulan
提出日時 2016-10-02 06:06:20
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,592 bytes
コンパイル時間 2,276 ms
コンパイル使用メモリ 185,848 KB
実行使用メモリ 19,072 KB
最終ジャッジ日時 2024-05-01 09:31:12
合計ジャッジ時間 10,358 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
19,072 KB
testcase_01 AC 3 ms
5,760 KB
testcase_02 AC 3 ms
5,760 KB
testcase_03 AC 3 ms
5,760 KB
testcase_04 AC 4 ms
5,888 KB
testcase_05 AC 3 ms
5,760 KB
testcase_06 AC 3 ms
5,760 KB
testcase_07 AC 9 ms
6,144 KB
testcase_08 AC 91 ms
6,912 KB
testcase_09 AC 33 ms
6,400 KB
testcase_10 AC 12 ms
6,016 KB
testcase_11 AC 51 ms
6,272 KB
testcase_12 AC 4 ms
5,888 KB
testcase_13 AC 15 ms
5,888 KB
testcase_14 AC 5 ms
5,760 KB
testcase_15 AC 7 ms
5,888 KB
testcase_16 AC 6 ms
6,016 KB
testcase_17 AC 53 ms
6,912 KB
testcase_18 AC 319 ms
9,088 KB
testcase_19 AC 442 ms
9,856 KB
testcase_20 AC 5 ms
6,144 KB
testcase_21 AC 763 ms
13,312 KB
testcase_22 TLE -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

typedef pair<int,int> pi;

struct UF{
    int n;
    //正だったらその頂点の親,負だったら根で連結成分の個数
    vector<int> d;
    UF() {}
    UF(int N):n(N), d(N,-1){}
    int root(int v){
        if(d[v]<0) return v;
        return d[v]=root(d[v]);
    }
    bool unite(int X,int Y){
        X=root(X); Y=root(Y);
        if(X==Y) return false;
        if(size(X) < size(Y)) swap(X,Y);
        d[X]+=d[Y];
        d[Y]=X;
        return true;
    }
    int size(int v){ return -d[root(v)]; }
};

int h,w;
int a[200][200];

// connected component
int cc[200][200];
int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};

// Graph
set<int> G[40000];
int col[40000];

int main()
{
    scanf(" %d %d", &h, &w);
    rep(i,h)rep(j,w) scanf(" %d", &a[i][j]);

    // BFS
    #define IN(x,y) (0<=x && x<w && 0<=y && y<h)
    memset(cc,-1,sizeof(cc));
    int cc_num=0;
    rep(y,h)rep(x,w)
    {
        if(cc[y][x]>=0) continue;

        queue<pi> que;
        que.push(pi(y,x));
        cc[y][x]=cc_num;
        while(!que.empty())
        {
            pi now=que.front();
            que.pop();
            rep(i,4)
            {
                int nx=now.se+dx[i], ny=now.fi+dy[i];
                if(IN(nx,ny) && a[ny][nx]==a[now.fi][now.se] && cc[ny][nx]==-1)
                {
                    cc[ny][nx]=cc_num;
                    que.push(pi(ny,nx));
                }
            }
        }

        ++cc_num;
    }

    // グラフ構成
    rep(y,h)rep(x,w)
    {
        col[cc[y][x]] = a[y][x];
        rep(i,4)
        {
            int nx=x+dx[i], ny=y+dy[i];
            if(IN(nx,ny) && cc[y][x]!=cc[ny][nx])
            {
                int p=cc[y][x], q=cc[ny][nx];
                G[p].insert(q);
                G[q].insert(p);
            }
        }
    }

    // rep(i,h)
    // {
    //     rep(j,w) printf("%3d", cc[i][j]);
    //     printf("\n");
    // }
    // rep(i,cc_num)
    // {
    //     printf(" %d(col=%d) :", i,col[i]);
    //     for(const int &j:G[i]) printf(" %d", j);
    //     printf("\n");
    // }

    UF uf(cc_num);

    // クエリ処理
    int Q;
    scanf(" %d", &Q);
    while(Q--)
    {
        int r,c,x;
        scanf(" %d %d %d", &r, &c, &x);
        --r;
        --c;

        if(x == col[ uf.root(cc[r][c]) ]) continue;

        set<int> newG;
        set<int> appear=G[ uf.root(cc[r][c]) ];
        appear.insert(uf.root(cc[r][c]));

        // printf(" merging: %d and", uf.root(cc[r][c]));
        for(const int &nx:G[uf.root(cc[r][c])])
        {
            // printf(" %d", uf.root(nx));
            for(const int &i:G[uf.root(nx)])
            {
                if(appear.find(i) == appear.end()) newG.insert(i);
            }
            uf.unite(uf.root(cc[r][c]),uf.root(nx));
        }
        // printf("\n");

        col[uf.root(cc[r][c])] = x;
        G[uf.root(cc[r][c])] = newG;

        // printf(" process: %d\n",Q);
        // rep(i,cc_num)
        // {
        //     printf(" %d(col=%d) :", i,col[i]);
        //     for(const int &j:G[i]) printf(" %d", j);
        //     printf("\n");
        // }
    }

    // 出力
    rep(y,h)
    {
        rep(x,w)
        {
            if(x) printf(" ");
            printf("%d", col[uf.root(cc[y][x])]);
        }
        printf("\n");
    }
    return 0;
}
0