| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 576462 |
2022-06-13T06:25:15 Z |
balbit |
Paint (COI20_paint) |
C++14 |
|
793 ms |
524288 KB |
#include <bits/stdc++.h>
//#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 2e5+5;
const int BS = 1000;
int color[maxn], sz[maxn],par[maxn];
vector<int> touch[maxn/BS+3][100005];
int touchpos[maxn];
int TID = 0;
vector<int> here[maxn];
int n,m;
inline int getid(int i, int j) {
return i*m+j;
}
int find(int x) {
return x == par[x] ? x : par[x] = find(par[x]);
}
int dx[] = {0,-1,0,1};
int dy[] = {1,0,-1,0};
inline bool ingrid(int r, int c) {
return r>=0&&r<n&&c>=0&&c<m;
}
bool tmpseen[maxn];
vector<int> getadj(int x) {
vector<int> re;
for (int e : here[x]) {
int er = e/m, ec = e%m;
REP(k,4) {
int tr = er + dx[k], tc = ec + dy[k];
if (ingrid(tr, tc)) {
int hi = find(getid(tr,tc));
if (!tmpseen[hi]) {
re.pb(hi); tmpseen[hi] = 1;
}
}
}
}
for (int y : re) tmpseen[y] = 0;
return re;
}
void mrg(int a, int b) {
a = find(a); b = find(b);
if (a == b) {
return;
}
assert(color[a] == color[b]);
if (SZ(here[a]) < SZ(here[b])) swap(a,b);
// merge b into a
bool yoink = 0;
if (SZ(here[a]) >= BS) {
int tpa = touchpos[a];
if (SZ(here[b]) >= BS) {
int tpb = touchpos[b];
// big - big
// brute force the entire array; at most sqrt of these merges
REP(r, 100002) {
touch[tpa][r].insert(touch[tpa][r].end(), ALL(touch[tpb][r]));
}
}else{
for (int hi : getadj(b)) {
if (color[hi] != color[a]) {
touch[tpa][color[hi]].pb(hi);
}else {
assert(hi == a || hi == b);
}
}
}
}else{
yoink = 1;
}
here[a].insert(here[a].end(), ALL(here[b]));
par[b] = a;
if (yoink && SZ(here[a]) >= BS) {
// upgrade it
int tpa = touchpos[a] = TID++;
for (int e : getadj(a)) {
if (color[e] != color[a]) {
touch[tpa][color[e]].pb(e);
}else{
assert(e == a);
}
}
}
}
void go(int id, int col) {
id = find(id);
int r = id/m, c = id%m;
color[id] = col;
vector<int> tomerge;
if (SZ(here[id]) >= BS) {
// yarrr i'm biggg
int tp = touchpos[id];
vector<int> todo;
for (int hm : touch[tp][col]) {
int hh = find(hm);
if (hh != id && color[hh] == col) {
if (!tmpseen[hh]) tomerge.pb(hh), tmpseen[hh] = 1;
}
}
touch[tp][col].clear();
vector<int>().swap(touch[tp][col]);
}else{
// smol boi
for (int hi : getadj(id)) {
if (hi != id && color[hi] == col) {
tomerge.pb(hi);
}
}
}
for (int t : tomerge) {
mrg(id, t);
tmpseen[t] = 0;
}
}
signed main(){
IOS();
cin>>n>>m;
vector<vector<int> > g;
g.resize(n, vector<int> (m,0));
REP(i,n) REP(j,m) {
cin>>g[i][j]; g[i][j];
here[getid(i,j)].pb(getid(i,j));
color[getid(i,j)] = g[i][j];
par[getid(i,j)] = getid(i,j);
}
REP(i,n) REP(j,m) {
REP(t,4) {
int I = i + dx[t], J = j + dy[t];
if (ingrid(I,J) && color[getid(i,j)] == color[getid(I,J)]) {
mrg(getid(i,j), getid(I,J));
}
}
}
int qu; cin>>qu;
REP(ar, qu) {
int r,c; cin>>r>>c;
--r; --c;
int ncol; cin>>ncol;
go(getid(r,c), ncol);
}
REP(i,n) REP(j,m) {
int it = getid(i,j);
bug(it, find(it));
if (find(it) == it) {
for (int e : here[it]) {
bug(e/m, e%m, color[it]);
g[e/m][e%m] = color[it];
}
}
}
REP(i,n) REP(j,m) {
cout<<g[i][j]<<" \n"[j==m-1];
}
}
Compilation message
paint.cpp: In function 'void go(int, int)':
paint.cpp:152:9: warning: unused variable 'r' [-Wunused-variable]
152 | int r = id/m, c = id%m;
| ^
paint.cpp:152:19: warning: unused variable 'c' [-Wunused-variable]
152 | int r = id/m, c = id%m;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
216 ms |
481664 KB |
Output is correct |
| 2 |
Correct |
250 ms |
481824 KB |
Output is correct |
| 3 |
Correct |
230 ms |
482124 KB |
Output is correct |
| 4 |
Runtime error |
729 ms |
524288 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
288 ms |
484128 KB |
Output is correct |
| 2 |
Runtime error |
793 ms |
524288 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
782 ms |
524288 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
782 ms |
524288 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
