이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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<(n+5)*(m+5);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];
Egs[gb]+=Egs[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]=2;
}
for(int j=1;j<=m;j++){
B[0][j]=B[n+1][j]=2;
}
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;
Egs[cur]=B[i+1][j]+B[i-1][j]+B[i][j+1]+B[i][j-1]-4;
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]);
}
}
}
}
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]/2>Sz[i])
return cout<<"No", 0;
else if(Egs[i]/2==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 'bool merge(long long int, long long int)':
covering.cpp:36:10: warning: value computed is not used [-Wunused-value]
36 | P[ga]==gb;
covering.cpp: In function 'int main()':
covering.cpp:97: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]
97 | for(int l1=0;l1<Cur.size();l1++){
| ~~^~~~~~~~~~~
covering.cpp:98: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]
98 | for(int l2=0;l2<Cur.size();l2++){
| ~~^~~~~~~~~~~
covering.cpp:107: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]
107 | for(int i=0;i<P.size();i++){
| ~^~~~~~~~~
covering.cpp:111:18: warning: division by zero [-Wdiv-by-zero]
111 | 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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |