| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 498481 | uncripted | T-Covering (eJOI19_covering) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define f first
#define se second
#define pb push_back
using namespace std;
int ss=0;
int size=0;
multiset<int> t;
int nsize=0;
int a[5000][5000];
int r[5000][5000];
int fix[5000][5000];
int gr[5000][5000];
int vis[5000][5000];
vector<pair<int,int> > adj[5000][5000];
void dfs(pair<int,int> p){
vis[p.f][p.se]=1;
nsize++;
if(vis[p.f-1][p.se]!=1){
size++;
}
if(vis[p.f+1][p.se]!=1){
size++;
}
if(vis[p.f][p.se-1]!=1){
size++;
}
if(vis[p.f][p.se+1]!=1){
size++;
}
t.insert(a[p.f-1][p.se]);
t.insert(a[p.f+1][p.se]);
t.insert(a[p.f][p.se-1]);
t.insert(a[p.f][p.se+1]);
vis[p.f-1][p.se]=1;
vis[p.f+1][p.se]=1;
vis[p.f][p.se-1]=1;
vis[p.f][p.se+1]=1;
for(int i=0; i<adj[p.f][p.se].size(); i++){
if(vis[adj[p.f][p.se][i].f][adj[p.f][p.se][i].se]){
continue;
}
dfs({adj[p.f][p.se][i].f, adj[p.f][p.se][i].se});
}
}
int main(){
int n,m;
cin>>n>>m;
for(int i=0; i<n; i++){
for (int j=0; j<m; j++){
cin>>a[i][j];
r[i][j]=0;
fix[i][j]=0;
gr[i][j]=0;
vis[i][j]=0;
}
}
int k;
cin>>k;
pair<int,int> c[k];
for(int i=0; i<k; i++){
cin>>c[i].f>>c[i].se;
r[c[i].f][c[i].se]=1;
}
int pas=0;
pair<int,int> d[8]={{1,1}, {1,0}, {1,-1}, {0,1}, {0, -1}, {-1,1}, {-1, 0}, {-1,-1}};
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
int p=0;
for(int ii=0; ii<8; ii++){
int x=i+d[ii].f;
int y=j+d[ii].se;
if(r[i][j]==1 && r[x][y]==1){
p++;
if(i+1>=n || i-1<0 || j-1<0 || j+1>=m || x+1>=n || x-1<0 || y-1<0 || y+1>=m){
cout<<"No"<<endl;
return 0;
}
fix[i][j]=1;
fix[i+1][j]=1;
fix [i-1][j]=1;
fix[i][j-1]=1;
fix[i][j+1]=1;
fix[x][y]=1;
fix[x+1][y]=1;
fix[x-1][y]=1;
fix[x][y-1]=1;
fix[x][y+1]=1;
}
}
if(p>1){
cout<<"No"<<endl;
return 0;
}
}
}
for(int asd=0; asd<k; asd++){
for(int i=0; i<k; i++){
int x=c[i].f,y=c[i].se;
if(fix[x][y]==1){
continue;
}
int bruh=4;
bool left=true,right=true,up=true,down=true;
if(x+1>=n){
bruh--;
up=false;
}else if(fix[x+1][y]==1 || r[x+1][y]==1){
bruh--;
up=false;
}
if(x-1<0){
bruh--;
down=false;
}else if(fix[x-1][y]==1 || r[x-1][y]==1){
bruh--;
down=false;
}
if(y-1<0){
bruh--;
left=false;
}else if(fix[x][y-1]==1 || r[x][y-1]==1){
bruh--;
left=false;
}
if( y+1>=m){
bruh--;
right=false;
}else if(fix[x][y+1]==1 || r[x][y+1]==1){
bruh--;
right=false;
}
if(bruh==3){
fix[x][y]=1;
if(up==true){
fix[x+1][y]=1;
}
if(down==true){
fix[x-1][y]=1;
}
if(left==true){
fix[x][y-1]=1;
}
if(right==true){
fix[x][y+1]=1;
}
}
if(bruh<3){
cout<<"No";
return 0;
}
if(bruh==4){
gr[x][y]=1;
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(gr[i][j]==0){
continue;
}
if(i+2<n){
if(gr[i+2][j]==1){
adj[i][j].pb({i+2,j});
}
}
if(i-2>=0){
if(gr[i-2][j]==1){
adj[i][j].pb({i-2,j});
}
}
if(j+2<m){
if(gr[i][j+2]==1){
adj[i][j].pb({i,j+2});
}
}
if(j-2>=0){
if(gr[i][j-2]==1){
adj[i][j].pb({i,j-2});
}
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(vis[i][j]==0 && gr[i][j]==1 ){
dfs({i,j});
if(size==3*nsize+1){
ss+=*t.begin();
}
if(size<3*nsize){
cout<<"No"<<endl;
return 0;
}
t.clear();
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(fix[i][j]==1 || vis[i][j]==1){
pas+=a[i][j];
}
}
}
cout<<pas-ss;
}