| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 576346 |
2022-06-13T04:01:45 Z |
czhang2718 |
Paint (COI20_paint) |
C++17 |
|
3000 ms |
109996 KB |
#include "bits/stdc++.h"
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
#define f first
#define s second
#define pb push_back
#define nl '\n'
#define sz(x) (int) x.size()
#define rep(i,a,b) for(int i=a; i<=b; i++)
const int N=200020;
const int B=500;
int r, c, q;
vi buffer;
// vi adj[N];
int dx[]={-1, 0, 0, 1};
int dy[]={0, -1, 1, 0};
// dsu
int par[N], par2[N];
int rnk[N];
int col[N];
vector<vi> g;
int deg[N];
map<int, vi> adj[N];
map<int, bool> edge[N];
bool touch[N];
int find(int x){
return par[x]==x?x:par[x]=find(par[x]);
}
bool join(int x, int y){
int a=find(x);
int co=col[a];
int b=find(y);
col[a]=col[b]=co;
if(a==b) return 0;
// cout << "join " << a/(c+1) << " " << a%(c+1) << " w " << b/(c+1) << " " << b%(c+1) << nl;
// if(rnk[a]!=rnk[b] && rnk[a]<rnk[b]) par[a]=b;
// else par[b]=a;
// if(rnk[a]==rnk[b]) rnk[a]++;
if(deg[a]>deg[b]) swap(a,b);
adj[b].insert(adj[a].begin(), adj[a].end());
edge[b].insert(edge[a].begin(), edge[a].end());
par[a]=b;
deg[b]+=deg[a];
return 1;
}
int h(int i, int j){
return (c+1)*i+j;
}
ll h2(int i,int j){
if(i>j) swap(i,j);
return ll(N)*i+j;
}
void create(){
unordered_map<ll, bool> mp;
// edge.clear();
// edge.reserve(N);
mp.reserve(4*r*c);
rep(i,1,r){
rep(j,1,c){
adj[h(i,j)].clear();
edge[h(i,j)].clear();
g[i][j]=col[find(h(i,j))];
par2[h(i,j)]=find(h(i,j));
// touch[h(i,j)]=0;
// cout << g[i][j] << " ";
deg[h(i,j)]=0;
}
// cout << nl;
}
// cout << nl;
rep(i,1,r){
rep(j,1,c){
rep(k,0,1){
int x=i+dx[k];
int y=j+dy[k];
if(!x || !y || x>r || y>c) continue;
if(g[i][j]!=g[x][y]) mp[{h2(find(h(i,j)), find(h(x,y)))}]=1;
// else assert(find(h(i,j))==find(h(x,y)));
// else{
// if(find(h(i,j))!=find(h(x,y))){
// cout << i << j << " " << x << y << nl;
// cout << "BAD\n";
// exit(0);
// }
// }
}
}
}
// adj.clear();
// adj.reserve(sz(mp)*2);
for(auto e:mp){
ll hash=e.f;
int u=hash/N;
int v=hash%N;
// cout << "adj " << u << " " << v << nl;
adj[u][col[find(v)]].pb(v);
adj[v][col[find(u)]].pb(u);
deg[u]++;
deg[v]++;
edge[u][v]=edge[v][u]=1;
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> r >> c;
g.resize(r+1, vi(c+1));
rep(i,1,r){
rep(j,1,c){
cin >> g[i][j];
par[h(i,j)]=h(i,j);
col[h(i,j)]=g[i][j];
rep(k,0,1){
int x=i+dx[k];
int y=j+dy[k];
if(!x || !y) continue;
if(g[i][j]==g[x][y]) join(h(i,j), h(x,y));
}
}
}
create();
cin >> q;
while(q--){
// cout << "Q " << q << nl;
int x, y, c;
cin >> x >> y >> c;
int u=find(h(x,y));
col[u]=c;
for(int i:buffer){
int co=col[find(i)];
if(co!=c) continue;
if(edge[u].find(i)!=edge[u].end()) join(u,i);
}
buffer.pb(u);
for(int v:adj[u][c]){
if(find(v)==find(u)) continue;
int real_c=col[find(v)];
if(real_c!=c) continue;
buffer.pb(v);
join(u,v);
}
if(sz(buffer)>B){
create();
buffer.clear();
}
}
create();
rep(i,1,r){
rep(j,1,c){
cout << g[i][j] << " ";
}
cout << nl;
}
}
// graph
// color node, merge neighbors with same color
// sqrt batch: no. merged nodes >= B -> recreate graph
// adj sets
// query: unordered map {u, {col=k}}
// + check newly changed nodes
// what if you change x, x, x, x
// dsu, par, col
// slow:
// iterate same adj, merge, call this set X
// keep list of neighbors of adj
// erase orig edges v->X
// for v:list, add v->root(X)
// optimize: touch[u]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
19540 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
19668 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3038 ms |
38384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
45 ms |
44824 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3043 ms |
109996 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
