제출 #805424

#제출 시각아이디문제언어결과실행 시간메모리
805424Essa2006T-Covering (eJOI19_covering)C++14
0 / 100
11 ms10352 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define FF first #define SS second #define all(a) a.begin(), a.end() #define mod (ll)(1000000007) const int inf=1e9; int n, m; vector<int>Sz, Egs, Mn, P; vector<vector<int>>A, B; void pre(){ Sz.clear(), Egs.clear(), Mn.clear(), A.clear(), B.clear(); Sz.resize((n+5)*(m+5)), Egs=P=Sz, Mn.resize((n+5)*(m+5), inf), A.resize(n+5, vector<int>(m+5)), B=A; for(int i=1;i<P.size();i++){ P[i]=i; } } int trans(int i, int j){ return i*(m+1)+j; } int find(int ind){ if(ind==P[ind]) return ind; P[ind]=find(P[ind]); } bool merge(int a, int b){ int ga=find(a), gb=find(b); if(ga==gb) return 0; if(rand()&1) swap(a, b); P[ga]=gb; Sz[gb]+=Sz[ga]; Mn[gb]=min(Mn[gb], Mn[ga]); return 1; } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>m; pre(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>A[i][j]; } } for(int i=1;i<=n;i++){ B[i][0]=B[i][m+1]=1; } for(int j=1;j<=m;j++){ B[0][j]=B[n+1][j]=1; } int q; cin>>q; while(q--){ int i, j; cin>>i>>j; i++, j++; B[i][j]+=inf; B[i+1][j]++, B[i-1][j]++; B[i][j+1]++, B[i][j-1]++; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(B[i][j]<inf) continue; int cur=trans(i, j); if(B[i+1][j]>=inf || B[i-1][j]>=inf || B[i][j-1]>=inf || B[i][j+1]>=inf) return cout<<"No", 0; Sz[cur]=1; if(B[i+1][j]==1) Mn[cur]=min(Mn[cur], A[i+1][j]); if(B[i-1][j]==1) Mn[cur]=min(Mn[cur], A[i-1][j]); if(B[i][j+1]==1) Mn[cur]=min(Mn[cur], A[i][j+1]); if(B[i][j-1]==1) Mn[cur]=min(Mn[cur], A[i][j-1]); } } for(int i=2;i<n;i++){ for(int j=2;j<m;j++){ vector<int>Cur; if(B[i+1][j]>=inf) Cur.push_back(trans(i+1, j)); if(B[i-1][j]>=inf) Cur.push_back(trans(i-1, j)); if(B[i][j+1]>=inf) Cur.push_back(trans(i, j+1)); if(B[i][j-1]>=inf) Cur.push_back(trans(i, j-1)); for(int l1=0;l1<Cur.size();l1++){ for(int l2=0;l2<Cur.size();l2++){ if(l1==l2) continue; merge(Cur[l1], Cur[l2]); } } } } for(int i=0;i<=n+1;i++){ for(int j=0;j<=m+1;j++){ if(B[i][j]>1 && B[i][j]<inf){ if(i && B[i-1][j]>=inf) Egs[find(trans(i-1, j))]+=B[i][j]-1; else if(i!=n+1 && B[i+1][j]>=inf) Egs[find(trans(i+1, j))]+=B[i][j]-1; else if(j && B[i][j-1]>=inf) Egs[find(trans(i, j-1))]+=B[i][j]-1; else if(j!=m+1 && B[i][j+1]>=inf) Egs[find(trans(i, j+1))]+=B[i][j]-1; } } } int ans=0; for(int i=0;i<P.size();i++){ if(i!=find(i)) continue; if(Egs[i]&1) Sz[i]/=0; if(Egs[i]>Sz[i]) return cout<<"No", 0; else if(Egs[i]==Sz[i]-1){ ans-=Mn[i]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(B[i][j]) ans+=A[i][j]; } } cout<<ans; }

컴파일 시 표준 에러 (stderr) 메시지

covering.cpp: In function 'void pre()':
covering.cpp:17:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=1;i<P.size();i++){
      |                 ~^~~~~~~~~
covering.cpp: In function 'int main()':
covering.cpp:95:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             for(int l1=0;l1<Cur.size();l1++){
      |                          ~~^~~~~~~~~~~
covering.cpp:96:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |                 for(int l2=0;l2<Cur.size();l2++){
      |                              ~~^~~~~~~~~~~
covering.cpp:119:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for(int i=0;i<P.size();i++){
      |                 ~^~~~~~~~~
covering.cpp:123:18: warning: division by zero [-Wdiv-by-zero]
  123 |             Sz[i]/=0;
covering.cpp: In function 'long long int find(long long int)':
covering.cpp:27:11: warning: control reaches end of non-void function [-Wreturn-type]
   27 |     P[ind]=find(P[ind]);
#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...