제출 #307276

#제출 시각아이디문제언어결과실행 시간메모리
307276HemimorT-Covering (eJOI19_covering)C++14
55 / 100
88 ms15992 KiB
#include <algorithm> #include <iostream> #include <iomanip> #include <numeric> #include <cassert> #include <vector> #include <random> #include <cmath> #include <queue> #include <set> #include <map> #define syosu(x) fixed<<setprecision(x) using namespace std; typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<int,int> P; typedef pair<double,double> pdd; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<double> vd; typedef vector<vd> vvd; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<string> vs; typedef vector<P> vp; typedef vector<vp> vvp; typedef vector<pll> vpll; typedef pair<int,P> pip; typedef vector<pip> vip; const int inf=1<<30; const ll INF=1ll<<60; const double pi=acos(-1); const double eps=1e-8; const ll mod=1e9+7; const int dx[8]={-1,0,1,0,1,1,-1,-1},dy[8]={0,1,0,-1,1,-1,1,-1}; vi vin(int n,int d=0){ vi a(n); for(int i=0;i<n;i++){ cin>>a[i]; a[i]-=d; } return a; } vl vlin(int n,int d=0){ vl a(n); for(auto &i:a){ cin>>i; i-=d; } return a; } vvi vvin(int n,int m){ vvi a(n,vi(m)); for(int i=0;i<n;i++) for(auto &j:a[i]) cin>>j; return a; } vvi gin(int n,int m,int d=1){ vvi g(n); for(int i=0;i<m;i++){ int u,v; cin>>u>>v; u-=d,v-=d; g[u].push_back(v); g[v].push_back(u); } return g; } void vout(vi a){ int n=a.size(); cout<<n<<" :"; for(auto i:a) cout<<' '<<i; cout<<endl; } void vvout(vvi a){ int n=a.size(); for(int i=0;i<n;i++) vout(a[i]); } bool ingrid(int x,int y,int n,int m){ return 0<=x&&x<n&&0<=y&&y<m; } int n,m,k; vvi a,b,c; vi x,y,used; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n>>m; a=vvin(n,m); b=vvi(n,vi(m,-1)); c=vvi(n,vi(m)); cin>>k; used=x=y=vi(k); for(int i=0;i<k;i++){ cin>>x[i]>>y[i]; b[x[i]][y[i]]=i; c[x[i]][y[i]]++; } if(c[0][0]||c[0][m-1]||c[n-1][0]||c[n-1][m-1]){ cout<<"No"<<endl; return 0; } for(int i=0;i<k;i++){ int B=0,t=0; for(int j=0;j<8;j++){ int X=x[i]+dx[j],Y=y[i]+dy[j]; if(!ingrid(X,Y,n,m)) B=1; else if(b[X][Y]>=0) t++; } t+=B; if(t>=2){ cout<<"No"<<endl; return 0; } if(t==0) continue; for(int j=0;j<4;j++){ int X=x[i]+dx[j],Y=y[i]+dy[j]; if(ingrid(X,Y,n,m)) c[X][Y]=1; } used[i]=1; } for(int i=0;i<k;i++) if(!used[i]){ int t=0; for(int j=0;j<4;j++){ int X=x[i]+dx[j],Y=y[i]+dy[j]; if(ingrid(X,Y,n,m)&&c[X][Y]) t++; } if(t==0) continue; queue<int> q; q.push(i); used[i]=1; while(!q.empty()){ int I=q.front();q.pop(); t=0; for(int j=0;j<4;j++){ int X=x[I]+dx[j],Y=y[I]+dy[j]; if(ingrid(X,Y,n,m)&&c[X][Y]) t++; } if(t>=2){ cout<<"No"<<endl; return 0; } for(int j=0;j<4;j++){ int X=x[I]+dx[j],Y=y[I]+dy[j]; if(ingrid(X,Y,n,m)) c[X][Y]=1; } for(int j=0;j<4;j++){ int X=x[I]+2*dx[j],Y=y[I]+2*dy[j]; if(ingrid(X,Y,n,m)&&b[X][Y]>=0&&!used[b[X][Y]]){ used[b[X][Y]]=1; q.push(b[X][Y]); } } } } for(int i=0;i<k;i++) if(!used[i]){ queue<int> q; q.push(i); used[i]=2; vi d; int M=0; while(!q.empty()){ int I=q.front();q.pop(); d.push_back(I); for(int j=0;j<4;j++){ int X=x[I]+2*dx[j],Y=y[I]+2*dy[j]; if(ingrid(X,Y,n,m)&&b[X][Y]>=0){ if(!used[b[X][Y]]){ used[b[X][Y]]=2; q.push(b[X][Y]); } else if(used[b[X][Y]]==2) M++; } } } // assert(M%2==0); M/=2; int N=d.size(); if(M>N){ cout<<"No"<<endl; return 0; } for(auto I:d) used[I]=1; if(N==M){ for(auto I:d){ for(int j=0;j<4;j++){ int X=x[I]+dx[j],Y=y[I]+dy[j]; if(ingrid(X,Y,n,m)) c[X][Y]=1; } } continue; } pip p={inf,{0,0}}; for(auto I:d){ for(int j=0;j<4;j++){ int X=x[I]+dx[j],Y=y[I]+dy[j]; if(ingrid(X,Y,n,m)) p=min(p,{a[X][Y],{X,Y}}); } } for(auto I:d){ for(int j=0;j<4;j++){ int X=x[I]+dx[j],Y=y[I]+dy[j]; if(ingrid(X,Y,n,m)){ if(p.second==make_pair(X,Y)) continue; c[X][Y]=1; } } } } int res=0; for(int i=0;i<n;i++) for(int j=0;j<m;j++) res+=a[i][j]*c[i][j]; cout<<res<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...