| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 577504 |
2022-06-14T22:39:11 Z |
czhang2718 |
Paint (COI20_paint) |
C++17 |
|
114 ms |
25664 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=200000;
const int B=500;
int r, c, q;
vector<vi> g;
int par[N];
int sz[N];
int col[N];
vi adj[N];
vi big;
map<int, set<int>> adj2[N];
int dx[]={-1, 0, 0, 1};
int dy[]={0, -1, 1, 0};
int find(int x){
return par[x]==x?x:par[x]=find(par[x]);
}
void join(int x, int y){
int a=find(x);
int b=find(y);
if(a==b) return;
if(sz[b]>sz[a]) swap(a,b);
if(sz[a]>B && sz[b]>B){
for(auto e:adj2[b]){
for(int k:e.s){
if(find(k)!=a && find(k)!=b && col[find(k)]==e.f) adj2[a][e.f].insert(find(k));
} // shouldn't need find(k)
}
}
else if(sz[a]>B && sz[b]<=B){
for(int k:adj[b]){
k=find(k);
int c=col[k];
if(k!=a && k!=b) adj2[a][c].insert(k);
}
}
else if(sz[a]+sz[b]<=B) {
for(int k:adj[b]) if(find(k)!=a && find(k)!=b) adj[a].pb(find(k));
}
if(sz[a]+sz[b]>B && sz[a]<=B){
big.pb(a);
for(int k:adj[b]){
if(find(k)!=a && find(k)!=b) adj2[a][col[find(k)]].insert(find(k));
}
}
par[b]=a;
sz[a]+=sz[b];
}
int h(int i, int j){
return c*i+j;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> r >> c;
g.resize(r, vi(c));
rep(i,0,r-1){
rep(j,0,c-1){
par[h(i,j)]=h(i,j);
sz[h(i,j)]=1;
rep(k,0,1){
int x=i+dx[k];
int y=j+dy[k];
if(x<0 || y<0) continue;
adj[h(i,j)].pb(h(x,y));
adj[h(x,y)].pb(h(i,j));
}
}
}
rep(i,0,r-1){
rep(j,0,c-1){
cin >> g[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<0 || y<0) continue;
if(g[i][j]==g[x][y]) join(h(i,j), h(x,y));
}
}
}
cin >> q;
while(q--){
int x, y, co;
cin >> x >> y >> co;
x--; y--;
int i=find(h(x,y));
int oldc=col[i];
col[i]=co;
if(sz[i]>B){
vi nei;
for(int p:adj2[i][co]) nei.pb(p);
adj2[i][co].clear();
for(int k:nei) if(col[find(k)]==co) join(i, k);
}
else{
vi nei;
for(int p:adj[i]) nei.pb(p);
for(int k:nei){
if(col[find(k)]==co) join(i, k);
}
}
int old=i;
i=find(i);
if(sz[i]<=B){
assert(adj[i].size()<=4*sz[i]);
for(int k:adj[i]){
k=find(k);
if(sz[k]>B && k!=i) adj2[k][co].insert(i);
}
}
else{
assert(big.size()<=r*c/B);
for(int j:big){
j=find(j);
if(j==i) continue;
if(adj2[j][oldc].find(old)!=adj2[j][oldc].end()) adj2[j][co].insert(i), adj2[j][oldc].erase(old);
}
}
}
rep(i,0,r-1){
rep(j,0,c-1){
cout << col[find(h(i,j))] << " ";
}
cout << nl;
}
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from paint.cpp:1:
paint.cpp: In function 'int main()':
paint.cpp:140:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
140 | assert(adj[i].size()<=4*sz[i]);
| ~~~~~~~~~~~~~^~~~~~~~~
paint.cpp:147:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
147 | assert(big.size()<=r*c/B);
| ~~~~~~~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
10 ms |
14424 KB |
Output is correct |
| 3 |
Correct |
15 ms |
14924 KB |
Output is correct |
| 4 |
Incorrect |
14 ms |
14932 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
18056 KB |
Output is correct |
| 2 |
Incorrect |
98 ms |
21060 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
114 ms |
25664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
103 ms |
24588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
