이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 200005
#define L(node) node * 2
#define R(node) node * 2 + 1
#define int long long
const int modulo = 1e9 + 7;
int32_t main()
{
fastio();
pii dir[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
pii dia[4] = {{1, 1}, {-1, -1}, {-1, 1}, {1, -1}};
int n, m;
cin>>n>>m;
int arr[n + 5][m + 5], done[n + 5][m + 5];
vector<pii> adj[n + 5][m + 5];
memset(done , -1, sizeof(done));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
cin>>arr[i][j], done[i][j] = 0;
}
int k;
cin>>k;
set<pii> spe;
int ans = 0;
for (int i = 1; i <= k; i++)
{
int x, y;
cin>>x>>y;
spe.insert({x + 1, y + 1});
done[x + 1][y + 1] = 2;
ans += arr[x + 1][y + 1];
}
//handle the ones that have only one way of placement
vector<pii> tmp(spe.begin(), spe.end());
for (auto i : tmp)
{
int x = i.st, y = i.nd;
int cnt = 0, mini = modulo;
for (int j = 0; j < 4; j++)
{
int a = dir[j].st, b = dir[j].nd;
if (done[x + a][y + b] == 0) cnt++, mini = min(mini, arr[x + a][y + b]);
}
if (cnt < 3)
{
cout<<"No\n";
return 0;
}
if (cnt == 3)
{
for (int j = 0; j < 4; j++)
{
int a = dir[j].st, b = dir[j].nd;
if (done[x + a][y + b] == 0) done[x + a][y + b] = 1, ans += arr[x + a][y + b];
}
done[x][y] = 1;
spe.erase(i);
continue;
}
}
//handle the diagonals, which have only one way of placement
tmp = vector<pii> (spe.begin(), spe.end());
for (auto i : tmp)
{
int x = i.st, y = i.nd;
if (done[x][y] == 1) continue;
int cnt = 0, mini = modulo;
pii ne;
for (int j = 0; j < 4; j++)
{
int a = dia[j].st, b = dia[j].nd;
if (done[x + a][y + b] == 2) cnt++, ne = {a, b};
}
if (cnt > 1)
{
cout<<"No\n";
return 0;
}
if (cnt == 1)
{
int c = ne.st, d = ne.nd;
done[x][y] = 1;
done[x + c][y + d] = 1;
spe.erase({x, y});
spe.erase({x + c, y + d});
cnt = 0;
for (int j = 0; j < 4; j++)
{
int a = dir[j].st, b = dir[j].nd;
if (done[x + a][y + b] == 0) cnt++, ans += arr[x + a][y + b], done[x + a][y + b] = 1;
}
if (done[x + 2 * c][y + d] == 0) cnt++, ans += arr[x + 2 * c][y + d], done[x + 2 * c][y + d] = 1;
if (done[x + c][y + 2 * d] == 0) cnt++, ans += arr[x + c][y + 2 * d], done[x + c][y + 2 * d] = 1;
if (cnt < 6)
{
cout<<"No\n";
return 0;
}
}
}
//handle the one that are left with one way of placement after placing the diagonals
tmp = vector<pii> (spe.begin(), spe.end());
for (auto i : tmp)
{
int x = i.st, y = i.nd;
int cnt = 0, mini = modulo;
for (int j = 0; j < 4; j++)
{
int a = dir[j].st, b = dir[j].nd;
if (done[x + a][y + b] == 0) cnt++, mini = min(mini, arr[x + a][y + b]);
}
if (cnt < 3)
{
cout<<"No\n";
return 0;
}
if (cnt == 3)
{
for (int j = 0; j < 4; j++)
{
int a = dir[j].st, b = dir[j].nd;
if (done[x + a][y + b] == 0) done[x + a][y + b] = 1, ans += arr[x + a][y + b];
}
done[x][y] = 1;
spe.erase(i);
continue;
}
}
//todo: handle the components which have one square between each other
tmp = vector<pii> (spe.begin(), spe.end());
for (auto i : tmp)
{
int x = i.st, y = i.nd;
for (int j = 0; j < 2; j++)
{
int a = dir[j].st * 2, b = dir[j].nd * 2;
if (x + a < 0 || y + b < 0) continue;
if (done[x + a][y + b] == 2) adj[x][y].pb({x + a, y + b}), adj[x + a][y + b].pb({x, y});
}
/*
cout<<x<<sp<<y<<" : "<<endl;
for (auto j : adj[x][y])
cout<<j.st<<sp<<j.nd<<endl;
*/
}
for (auto i : tmp)
{
int c = i.st, d = i.nd;
if (done[c][d] == 1) continue;
queue<pii> q;
q.push({c, d});
int mini = modulo, cnt = 0;
long long tot = 0;
int steps = 0;
pii ne;
while(!q.empty())
{
int x = q.front().st, y = q.front().nd;
done[x][y] = 1;
tot = tot + 1;
//cout<<x<<sp<<y<<endl;
spe.erase({x, y});
q.pop();
for (int j = 0; j < 4; j++)
{
int a = dir[j].st, b = dir[j].nd;
if (done[x + a][y + b] == 0)
{
if (arr[x + a][y + b] < mini) ne = {x + a, y + b};
cnt++, mini = min(mini, arr[x + a][y + b]);
ans += arr[x + a][y + b];
done[x + a][y + b] = 1;
}
}
for (int j = 0; j < adj[x][y].size(); j++)
{
int a = adj[x][y][j].st, b = adj[x][y][j].nd;
if (done[a][b] != 1) q.push({a, b}), done[a][b] = 1;
}
}
if (cnt < tot * 3)
{
//cout<<cnt<<sp<<tot<<endl;
cout<<"No\n";
return 0;
}
if (cnt > tot * 3)
{
done[ne.st][ne.nd] = 0;
ans -= arr[ne.st][ne.nd];
}
}
//todo: choose the minimum ones
tmp = vector<pii> (spe.begin(), spe.end());
for (auto i : tmp)
{
int x = i.st, y = i.nd;
int cnt = 0, mini = modulo;
pii ne;
for (int j = 0; j < 4; j++)
{
int a = dir[j].st, b = dir[j].nd;
if (done[x + a][y + b] == 0)
{
if (mini > arr[x + a][y + b]) ne = {x + a, y + b};
cnt++, mini = min(mini, arr[x + a][y + b]), ans += arr[x + a][y + b], done[x + a][y + b] = 1;
}
}
if (cnt < 3)
{
cout<<"No\n";
return 0;
}
done[x][y] = 1;
spe.erase(i);
if (cnt == 4)
{
done[ne.st][ne.nd] = 0;
ans -= arr[ne.st][ne.nd];
}
}
cout<<ans<<endl;
cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}
컴파일 시 표준 에러 (stderr) 메시지
covering.cpp: In function 'int32_t main()':
covering.cpp:80:16: warning: unused variable 'mini' [-Wunused-variable]
80 | int cnt = 0, mini = modulo;
| ^~~~
covering.cpp:191:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
191 | for (int j = 0; j < adj[x][y].size(); j++)
| ~~^~~~~~~~~~~~~~~~~~
covering.cpp:169:7: warning: unused variable 'steps' [-Wunused-variable]
169 | int steps = 0;
| ^~~~~
# | 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... |