oj.uz

Submission #562840

# Submission time Handle Problem Language Result Execution time Memory
562840 2022-05-15T11:35:53 Z Redhood Paint (COI20_paint) C++14
8 / 100
 3000 ms 236368 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#define fi first
#define se second
#define sz(x) (int)(x).size()
#define pb push_back
#define mkp make_pair


using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;






typedef long long ll;
typedef long double ld;



vector < vector < int > > g;


const int N = (int)2e5 + 10;
const int buben = 10001;


vector < int > neighbours[N];
int sz[N], cur_color[N] ,p[N] , r , s;
bool large[N];
unordered_map < int , vector < int > > bycolor[N];
unordered_set < int > big[N];

bool valid(int x , int y){
    if(x >= 0 && x < r && y >= 0 && y < s)
        return true;
    return false;
}
void make(int v, int C){
    p[v] = v;
    sz[v] = 1;
    cur_color[v] = C;
}
int fin(int v){
    if(p[v] == v)return v;
    return p[v] = fin(p[v]);
}
void un(int a , int b){
    a = fin(a) , b = fin(b);
    if(a == b)
        return;
    if(sz[a] < sz[b])
        swap(a , b);
    sz[a] += sz[b];
    p[b] = a;

    for(auto &u : neighbours[b])
        neighbours[a].pb(u);
    if(!large[a]){
        for(auto &f : big[b]){
            int u = fin(u);
            if(u != a)
                big[a].insert(u);
        }
    }

    if(sz[a] > buben){
        large[a] = 1;
        for(auto &u : neighbours[a]){
            u = fin(u);
            if(u != a){
                bycolor[a][cur_color[u]].push_back(u);
            }
        }
    }
}
/// so
void makeit(int x , int y , int c){
    int cell = fin(x * s + y);
    vector < int > unite_with;
    if(large[cell]){
        unite_with=bycolor[cell][c];
        bycolor[cell][c].clear();
    }else{
        for(auto &u : neighbours[cell]){
            u = fin(u);
            if(u != cell && cur_color[u] == c){
                unite_with.push_back(u);
            }
        }
    }
    for(auto &x : unite_with)
        un(cell , x);
    cell = fin(cell);
    cur_color[cell] = c;
    if(!large[cell]){
        for(auto &u : big[cell]){
            bycolor[u][c].push_back(cell);
        }
    }


}
vector < pair < int , int > > dir = {{-1 ,0}, {+1 , 0}, {0 , -1} , {0 , + 1}};
void find_neighb(int x , int y){
    for(auto &u : dir){
        int i = x + u.fi, j  = y + u.se;
        if(valid(i , j) && g[i][j] != g[x][y]){
            neighbours[x * s + y].pb(i * s + j);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    cin >> r >> s;
    g.resize(r , vector < int > (s));
    for(int i = 0; i < r; ++i){
        for(int j = 0; j < s; ++j){
            cin >> g[i][j];
        }
    }
    for(int i = 0; i < r; ++i){
        for(int j =0 ; j < s; ++j){
            make(i * s + j, g[i][j]);
            find_neighb(i , j);
        }
    }
    for(int i = 0; i < r; ++i){
        for(int j = 0; j < s; ++j){
            for(auto &u : dir){
                int a = i + u.fi , b = j + u.se;
                if(valid(a , b) && g[a][b] == g[i][j]){
                    un(a * s + b , i * s + j);
                }
            }
        }
    }

    int q;
    cin >> q;
    for(int i = 0; i < q; ++i){
        int x , y , c;
        cin >> x >> y >> c;
        --x, --y;
        makeit(x , y , c);
    }
    for(int i = 0; i < r; ++i){
        for(int j = 0; j < s; ++j){
            cout << cur_color[fin(i * s + j)] << ' ';
        }
        cout << '\n';
    }





    return 0;
}

Compilation message

paint.cpp: In function 'void un(int, int)':
paint.cpp:65:19: warning: unused variable 'f' [-Wunused-variable]
   65 |         for(auto &f : big[b]){
      |                   ^
paint.cpp:50:11: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |     if(p[v] == v)return v;
      |        ~~~^
paint.cpp:66:17: note: 'u' was declared here
   66 |             int u = fin(u);
      |                 ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 26956 KB Output is correct
2 Correct 16 ms 26972 KB Output is correct
3 Correct 20 ms 27476 KB Output is correct
4 Correct 23 ms 27592 KB Output is correct
5 Correct 139 ms 27828 KB Output is correct
6 Correct 143 ms 27820 KB Output is correct
7 Correct 16 ms 27092 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 29800 KB Output is correct
2 Correct 115 ms 34348 KB Output is correct
3 Execution timed out 3016 ms 37224 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3076 ms 44840 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 3088 ms 236368 KB Time limit exceeded
2 Halted 0 ms 0 KB -