| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 576522 |
2022-06-13T07:11:28 Z |
balbit |
Paint (COI20_paint) |
C++14 |
|
647 ms |
28248 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 = 300;
int color[maxn], sz[maxn],par[maxn];
map<int, set<int> > touch[maxn/BS+3];
int touchpos[maxn];
int TID = 0;
vector<int> here[maxn];
bool adj[maxn/BS+3][maxn/BS+3];
int whose[maxn/BS+3];
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
for (auto &e : touch[tpb]) {
for (int r : e.s) touch[tpa][e.f].insert(r);
}
map<int, set<int> > () . swap(touch[tpb]);
REP(k, TID) {
if (adj[tpb][k]) adj[tpa][k] = adj[k][tpa] = 1;
}
// REP(r, 100002) {
// touch[tpa][r].insert(touch[tpa][r].end(), ALL(touch[tpb][r]));
// vector<int>().swap(touch[tpa][r]);
// }
}else{
for (int hi : getadj(b)) {
if (color[hi] != color[a]) {
if (touchpos[hi] != -1) {
adj[tpa][touchpos[hi]] = adj[touchpos[hi]][tpa] = 1;
}else{
touch[tpa][color[hi]].insert(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
whose[TID] = a;
int tpa = touchpos[a] = TID++;
for (int e : getadj(a)) {
if (color[e] != color[a]) {
if (touchpos[e] != -1) {
adj[tpa][touchpos[e]] = adj[touchpos[e]][tpa] = 1;
}else{
touch[tpa][color[e]].insert(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;
if (touch[tp].count(col)) 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();
set<int>().swap(touch[tp][col]);
touch[tp].erase(col);
REP(j, TID) {
int who = whose[j];
if (tp!=j && (adj[j][tp]||adj[tp][j]) && par[who] == who && color[who] == col) {
if (!tmpseen[who]) tomerge.pb(who), tmpseen[who] = 1;
}
}
}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;
}
id = find(id);
if (SZ(here[id]) < BS) {
for (int hi : getadj(id)) {
if (hi != id && color[hi] != col && touchpos[hi] != -1) {
touch[touchpos[hi]][col].insert(id);
}
}
}
}
signed main(){
IOS();
memset(touchpos, -1, sizeof touchpos);
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:172:9: warning: unused variable 'r' [-Wunused-variable]
172 | int r = id/m, c = id%m;
| ^
paint.cpp:172:19: warning: unused variable 'c' [-Wunused-variable]
172 | int r = id/m, c = id%m;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5844 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5844 KB |
Output is correct |
| 3 |
Correct |
10 ms |
6292 KB |
Output is correct |
| 4 |
Correct |
16 ms |
6228 KB |
Output is correct |
| 5 |
Correct |
18 ms |
6996 KB |
Output is correct |
| 6 |
Correct |
14 ms |
6524 KB |
Output is correct |
| 7 |
Correct |
4 ms |
5816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
8180 KB |
Output is correct |
| 2 |
Correct |
160 ms |
12228 KB |
Output is correct |
| 3 |
Correct |
115 ms |
17416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
167 ms |
16668 KB |
Output is correct |
| 2 |
Correct |
154 ms |
16304 KB |
Output is correct |
| 3 |
Correct |
139 ms |
17044 KB |
Output is correct |
| 4 |
Correct |
220 ms |
17184 KB |
Output is correct |
| 5 |
Correct |
150 ms |
16456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
13400 KB |
Output is correct |
| 2 |
Correct |
379 ms |
28248 KB |
Output is correct |
| 3 |
Correct |
415 ms |
24344 KB |
Output is correct |
| 4 |
Correct |
459 ms |
26576 KB |
Output is correct |
| 5 |
Correct |
503 ms |
21816 KB |
Output is correct |
| 6 |
Correct |
188 ms |
18424 KB |
Output is correct |
| 7 |
Correct |
150 ms |
18488 KB |
Output is correct |
| 8 |
Correct |
157 ms |
18396 KB |
Output is correct |
| 9 |
Correct |
647 ms |
23772 KB |
Output is correct |
