oj.uz

Submission #412011

# Submission time Handle Problem Language Result Execution time Memory
412011 2021-05-26T12:11:41 Z 반딧불(#7584) Paint (COI20_paint) C++17
0 / 100
 3000 ms 14360 KB 
#include <bits/stdc++.h>
#define LIM 100000

using namespace std;

typedef long long ll;

int n, m;
int arr[200002];

vector<int> link[200002];
int par[200002], sz[200002];
int bigIndex[200002], bigInfo[400000/LIM+3], bigCnt;
bool chk[400000/LIM+3][200002];
bool nonsense[400000/LIM+3];

int find(int x){
    if(x == par[x]) return x;
    return par[x] = find(par[x]);
}

void merge(int x, int y){
    x = find(x), y = find(y);
    if(x==y) return;
    if(sz[x] < sz[y]) swap(x, y);
    par[y] = x, sz[x] += sz[y];

    int laterSum = (int)link[x].size() + (int)link[y].size();
    if(laterSum <= LIM){
        if((int)link[x].size() < (int)link[y].size()) link[x].swap(link[y]);
        for(auto tmp: link[y]){
            tmp = find(tmp);
            if(tmp == x) continue;
            link[x].push_back(tmp);
        }
    }
    else if(link[x].size() > LIM){
        for(auto tmp: link[y]){
            tmp = find(tmp);
            if(tmp == x) continue;
            link[x].push_back(tmp);
            chk[bigIndex[x]][tmp] = 1;
        }
        if((int)link[y].size() > LIM) nonsense[bigIndex[y]] = 1;
    }
    else if(link[y].size() > LIM){
        bigIndex[x] = bigIndex[y];
        bigInfo[bigIndex[x]] = x;
        link[x].swap(link[y]);
        for(auto tmp: link[y]){
            tmp = find(tmp);
            if(tmp == x) continue;
            link[x].push_back(tmp);
            chk[bigIndex[x]][tmp] = 1;
        }
    }
    else{
        int pnt = bigCnt++;
        bigIndex[x] = pnt;
        bigInfo[pnt] = x;
        for(auto &tmp: link[x]){
            tmp = find(tmp);
            chk[pnt][tmp] = 1;
        }
        for(auto tmp: link[y]){
            tmp = find(tmp);
            if(tmp == x) continue;
            link[x].push_back(tmp);
            chk[pnt][tmp] = 1;
        }
    }
    link[y].clear();
    link[y].shrink_to_fit();

    for(int i=0; i<bigCnt; i++){
        if(chk[i][y]) chk[i][x] = 1;
    }
}

void input(){
    scanf("%d %d", &n, &m);
    for(int i=0; i<n*m; i++) scanf("%d", &arr[i]);

    for(int i=0; i<n*m; i++){
        int r = i/m, c = i%m;
        par[i] = i, sz[i] = 1;
        if(r) link[i].push_back(i-m), link[i-m].push_back(i);
        if(c) link[i].push_back(i-1), link[i-1].push_back(1);
    }

    for(int i=0; i<n*m; i++){
        int r = i/m, c = i%m;
        if(r && arr[i] == arr[i-m]) merge(i, i-m);
        if(c && arr[i] == arr[i-1]) merge(i, i-1);
    }
}

void operate(){
    int q;
    scanf("%d", &q);
    while(q--){
        int p, c;
        scanf("%d %d", &p, &c);
        p = find((p-1)*m+(c-1));
        scanf("%d", &c);

        reverb1:
        for(int i=0; i<bigCnt; i++){
            if(!nonsense[i] && chk[i][p] && arr[bigInfo[i]] == arr[p] && bigInfo[i] != p){
                merge(bigInfo[i], p);
                p = find(p);
                goto reverb1;
            }
        }
        arr[p] = c;

        reverb2:
        for(auto &nxt: link[p]){
            nxt = find(nxt);
            if(arr[nxt] == arr[p] && nxt != p){
                merge(nxt, p);
                p = find(p);
                goto reverb2;
            }
        }
    }
}

void output(){
    for(int i=0; i<n*m; i++){
        printf("%d ", arr[find(i)]);
        if(i%m == m-1) puts("");
    }
}

int main(){
    input();
    operate();
    output();
}

Compilation message

paint.cpp: In function 'void input()':
paint.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
paint.cpp:82:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     for(int i=0; i<n*m; i++) scanf("%d", &arr[i]);
      |                              ~~~~~^~~~~~~~~~~~~~~
paint.cpp: In function 'void operate()':
paint.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
paint.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         scanf("%d %d", &p, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~
paint.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         scanf("%d", &c);
      |         ~~~~~^~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3074 ms 7512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3020 ms 14360 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3078 ms 12032 KB Time limit exceeded
2 Halted 0 ms 0 KB -