이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int N = (1<<20) + 1;
vector<int> nei[N];
int n,m,k;
int r[N];
int c[N];
int Seen[N];
vector<vector<int>> seen,g;
bool valid(int i,int j){
return (i>=1 and j>=1 and i<=n and j<=m);
}
vector<pair<int,int>> v = {{-1,-1},{-1,1},{1,-1},{1,1},{-2,0},{2,0},{0,2},{0,-2},{0,0},{0,1},{0,-1},{1,0},{-1,0}},vvv = {{0,0},{0,1},{0,-1},{1,0},{-1,0}};
void make_graph(){
for (int i=1;i<=k;i++){
for (auto [a,b] : v){
int nr = r[i] + a;
int nc = c[i] + b;
if (valid(nr,nc) and seen[nr][nc]!=0){
nei[i].push_back(seen[nr][nc]);
nei[seen[nr][nc]].push_back(i);
}
}
}
}
set<vector<int>> s;
int sz = 0;
int sum = 0;
int Mn;
void dfs(int i){
// cout<<i<<endl;
Seen[i] = true;
sz++;
for (auto [a,b] : vvv){
int nr = r[i] + a;
int nc = c[i] + b;
if (!valid(nr,nc) or s.find({nr,nc})!=s.end())
continue;
Mn = min(Mn,g[nr][nc]);
sum += g[nr][nc];
// cout<<"added "<<g[nr][nc]<<endl;
s.insert({nr,nc});
}
for (int u : nei[i])
if (!Seen[u])
dfs(u);
}
signed main(){
cin>>n>>m;
g.resize(n+5,vector<int> (m+5,0));
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
cin>>g[i][j];
cin>>k;
seen.resize(n+5,vector<int> (m+5,0));
for (int i=1;i<=k;i++){
cin>>r[i]>>c[i];
r[i]++;
c[i]++;
seen[r[i]][c[i]] = i;
}
make_graph();
int ans = 0;
for (int i=1;i<=k;i++){
if (!Seen[i]){
s.clear();
Mn = 10005;
sum = 0;
sz = 0;
dfs(i);
if (s.size()<4*sz){
// for (auto q : s)
// cout<<q[0]<<" "<<q[1]<<endl;
cout<<"No"<<endl;
return 0;
}
ans += sum;
if (s.size() > 4 * sz){
ans -= Mn;
// cout<<"removed Mn == "<<Mn<<endl;
}
}
}
cout<<ans<<endl;
}
컴파일 시 표준 에러 (stderr) 메시지
covering.cpp: In function 'int main()':
covering.cpp:97:16: warning: comparison of integer expressions of different signedness: 'std::set<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
97 | if (s.size()<4*sz){
| ~~~~~~~~^~~~~
covering.cpp:104:17: warning: comparison of integer expressions of different signedness: 'std::set<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
104 | if (s.size() > 4 * sz){
| ~~~~~~~~~^~~~~~~~
# | 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... |