oj.uz

답안 #562841

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
562841 2022-05-15T11:37:23 Z Redhood Paint (COI20_paint) C++14
8 / 100
 3000 ms 200648 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 = 320;


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]){
        for(auto &u : bycolor[cell][c]){
            if(cur_color[fin(u)] == c)
                unite_with.pb(fin(u));
        }
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 26964 KB Output is correct
2 Correct 21 ms 26964 KB Output is correct
3 Correct 19 ms 27364 KB Output is correct
4 Correct 28 ms 28672 KB Output is correct
5 Correct 1295 ms 200648 KB Output is correct
6 Correct 272 ms 57164 KB Output is correct
7 Correct 16 ms 26836 KB Output is correct

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 29640 KB Output is correct
2 Incorrect 120 ms 34148 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3082 ms 45972 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3094 ms 181472 KB Time limit exceeded
2 Halted 0 ms 0 KB -