#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("avx2","popcnt","rdrnd","bmi2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e6+7, INF=1e9+7;
int d[]={0, 1, -1}, F[LIM], mi[LIM], ok[LIM];
int dx[]={0, 1, 0, -1}, dy[]={1, 0, -1, 0};
queue<pair<int,int>>q;
vector<int>V[LIM];
int odw[LIM], ile_kraw, ile;
void DFS(int x, int o) {
odw[x]=0;
ile_kraw+=V[x].size();
++ile;
for(auto i : V[x]) if(odw[i]) DFS(i, x);
}
void zmien(int n, int m, int i, int j, int** T, int** ile_wolnych, int** czy_srodek,
int** uzyte) {
if(uzyte[i][j]==1) return;
rep(a, 4) if(0<=i+dx[a] && i+dx[a]<n && 0<=j+dy[a] && j+dy[a]<m) {
--ile_wolnych[i+dx[a]][j+dy[a]];
if(uzyte[i+dx[a]][j+dy[a]]) continue;
if(ile_wolnych[i+dx[a]][j+dy[a]]<4 && czy_srodek[i+dx[a]][j+dy[a]]) {
q.push({i+dx[a], j+dy[a]});
}
}
uzyte[i][j]=1;
}
int fnd(int x) {
if(F[x]==x) return x;
return F[x]=fnd(F[x]);
}
void uni(int a, int b) {
mi[fnd(a)]=min(mi[fnd(a)], mi[fnd(b)]);
F[fnd(b)]=fnd(a);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
int** T = new int*[n];
int** ile_wolnych = new int*[n];
int** uzyte = new int*[n];
int** czy_srodek = new int*[n];
rep(i, n) {
T[i]=new int[m];
ile_wolnych[i]=new int[m];
uzyte[i]=new int[m];
czy_srodek[i]=new int[m];
}
rep(i, n) {
rep(j, m) {
cin >> T[i][j];
ile_wolnych[i][j]=INF;
uzyte[i][j]=0;
czy_srodek[i][j]=0;
}
}
int k;
cin >> k;
if(min(n, m)==1) {
cout << "No\n";
return 0;
}
rep(i, k) {
int a, b;
cin >> a >> b;
czy_srodek[a][b]=1;
if((a==0 || a==n-1) && (b==0 || b==m-1)) {
cout << "No\n";
return 0;
}
ile_wolnych[a][b]=4;
if(a==0 || a==n-1 || b==0 || b==m-1) --ile_wolnych[a][b];
if(ile_wolnych[a][b]==3) q.push({a, b});
}
rep(i, n) rep(j, m) if(czy_srodek[i][j]) {
int ile_sasiadow=-1;
int x=-1, y=-1;
rep(a, 3) rep(b, 3) if(0<=i+d[a] && i+d[a]<=n-1 && 0<=j+d[b] && j+d[b]<=m-1) {
if(czy_srodek[i+d[a]][j+d[b]]) {
++ile_sasiadow;
x=i+d[a];
y=j+d[b];
}
}
if(ile_sasiadow==0) continue;
if(ile_sasiadow>1) {
cout << "No\n";
return 0;
}
if(i==0 || i==n-1 || j==0 || j==m-1 || x==0 || x==n-1 || y==0 || y==m-1) {
cout << "No\n";
return 0;
}
if(uzyte[i][j]) continue;
rep(a, 4) if(uzyte[i+dx[a]][j+dy[a]] || uzyte[x+dx[a]][y+dy[a]]) {
cout << "No\n";
return 0;
}
rep(a, 4) {
zmien(n, m, i+dx[a], j+dy[a], T, ile_wolnych, czy_srodek, uzyte);
zmien(n, m, x+dx[a], y+dy[a], T, ile_wolnych, czy_srodek, uzyte);
}
zmien(n, m, i, j, T, ile_wolnych, czy_srodek, uzyte);
zmien(n, m, x, y, T, ile_wolnych, czy_srodek, uzyte);
}
while(!q.empty()) {
int i=q.front().st, j=q.front().nd; q.pop();
if(uzyte[i][j]) continue;
if(ile_wolnych[i][j]<3) {
cout << "No\n";
return 0;
}
zmien(n, m, i, j, T, ile_wolnych, czy_srodek, uzyte);
rep(a, 4) if(0<=i+dx[a] && i+dx[a]<n && 0<=j+dy[a] && j+dy[a]<m) {
zmien(n, m, i+dx[a], j+dy[a], T, ile_wolnych, czy_srodek, uzyte);
}
}
rep(i, n) rep(j, m) if(czy_srodek[i][j] && !uzyte[i][j]) {
F[i*m+j]=i*m+j;
mi[i*m+j]=INF;
ok[i*m+j]=1;
rep(a, 4) mi[i*m+j]=min(mi[i*m+j], T[i+dx[a]][j+dy[a]]);
}
rep(i, n) rep(j, m) if(!uzyte[i][j] && czy_srodek[i][j]) {
if(i+2<n && czy_srodek[i+2][j]) {
uni(i*m+j, (i+2)*m+j);
V[i*m+j].pb((i+2)*m+j);
V[(i+2)*m+j].pb(i*m+j);
odw[i*m+j]=1;
odw[(i+2)*m+j]=1;
}
if(j+2<m && czy_srodek[i][j+2]) {
uni(i*m+j, i*m+j+2);
V[i*m+j].pb(i*m+j+2);
V[i*m+j+2].pb(i*m+j);
odw[i*m+j]=1;
odw[i*m+j+2]=1;
}
}
int sum=0;
rep(i, n) rep(j, m) if(odw[i*m+j]) {
ile_kraw=ile=0;
DFS(i*m+j, i*m+j);
ile_kraw/=2;
if(ile_kraw>ile) {
cout << "No\n";
return 0;
} else if(ile_kraw==ile) sum+=mi[fnd(i*m+j)];
}
rep(i, n) rep(j, m) if(czy_srodek[i][j] && !uzyte[i][j]) {
zmien(n, m, i, j, T, ile_wolnych, czy_srodek, uzyte);
rep(a, 4) if(0<=i+dx[a] && i+dx[a]<n && 0<=j+dy[a] && j+dy[a]<m) {
zmien(n, m, i+dx[a], j+dy[a], T, ile_wolnych, czy_srodek, uzyte);
}
}
rep(i, n) rep(j, m) {
if(uzyte[i][j]) sum+=T[i][j];
if(ok[i*m+j] && fnd(i*m+j)==i*m+j) sum-=mi[i*m+j];
}
cout << sum << '\n';
}
Compilation message
covering.cpp:2: warning: ignoring '#pragma GCC option' [-Wunknown-pragmas]
2 | #pragma GCC option("arch=native","tune=native","no-zero-upper")
|
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
24140 KB |
Output is correct |
2 |
Correct |
18 ms |
24524 KB |
Output is correct |
3 |
Correct |
26 ms |
26220 KB |
Output is correct |
4 |
Correct |
48 ms |
31392 KB |
Output is correct |
5 |
Correct |
131 ms |
46968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
24140 KB |
Output is correct |
2 |
Correct |
18 ms |
24228 KB |
Output is correct |
3 |
Correct |
25 ms |
26084 KB |
Output is correct |
4 |
Correct |
48 ms |
31392 KB |
Output is correct |
5 |
Correct |
122 ms |
46968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
24068 KB |
Output is correct |
2 |
Correct |
18 ms |
24612 KB |
Output is correct |
3 |
Correct |
30 ms |
26060 KB |
Output is correct |
4 |
Correct |
48 ms |
31384 KB |
Output is correct |
5 |
Correct |
123 ms |
46840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
23756 KB |
Output is correct |
2 |
Correct |
15 ms |
23844 KB |
Output is correct |
3 |
Correct |
20 ms |
24636 KB |
Output is correct |
4 |
Correct |
20 ms |
24316 KB |
Output is correct |
5 |
Correct |
32 ms |
25444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
23884 KB |
Output is correct |
2 |
Correct |
14 ms |
23756 KB |
Output is correct |
3 |
Correct |
17 ms |
23832 KB |
Output is correct |
4 |
Correct |
15 ms |
23756 KB |
Output is correct |
5 |
Correct |
16 ms |
23772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
24140 KB |
Output is correct |
2 |
Correct |
18 ms |
24524 KB |
Output is correct |
3 |
Correct |
26 ms |
26220 KB |
Output is correct |
4 |
Correct |
48 ms |
31392 KB |
Output is correct |
5 |
Correct |
131 ms |
46968 KB |
Output is correct |
6 |
Correct |
16 ms |
24140 KB |
Output is correct |
7 |
Correct |
18 ms |
24228 KB |
Output is correct |
8 |
Correct |
25 ms |
26084 KB |
Output is correct |
9 |
Correct |
48 ms |
31392 KB |
Output is correct |
10 |
Correct |
122 ms |
46968 KB |
Output is correct |
11 |
Correct |
15 ms |
24068 KB |
Output is correct |
12 |
Correct |
18 ms |
24612 KB |
Output is correct |
13 |
Correct |
30 ms |
26060 KB |
Output is correct |
14 |
Correct |
48 ms |
31384 KB |
Output is correct |
15 |
Correct |
123 ms |
46840 KB |
Output is correct |
16 |
Correct |
15 ms |
23756 KB |
Output is correct |
17 |
Correct |
15 ms |
23844 KB |
Output is correct |
18 |
Correct |
20 ms |
24636 KB |
Output is correct |
19 |
Correct |
20 ms |
24316 KB |
Output is correct |
20 |
Correct |
32 ms |
25444 KB |
Output is correct |
21 |
Correct |
16 ms |
24028 KB |
Output is correct |
22 |
Correct |
18 ms |
24572 KB |
Output is correct |
23 |
Correct |
26 ms |
26444 KB |
Output is correct |
24 |
Correct |
49 ms |
31392 KB |
Output is correct |
25 |
Correct |
122 ms |
47116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
24140 KB |
Output is correct |
2 |
Correct |
18 ms |
24524 KB |
Output is correct |
3 |
Correct |
26 ms |
26220 KB |
Output is correct |
4 |
Correct |
48 ms |
31392 KB |
Output is correct |
5 |
Correct |
131 ms |
46968 KB |
Output is correct |
6 |
Correct |
16 ms |
24140 KB |
Output is correct |
7 |
Correct |
18 ms |
24228 KB |
Output is correct |
8 |
Correct |
25 ms |
26084 KB |
Output is correct |
9 |
Correct |
48 ms |
31392 KB |
Output is correct |
10 |
Correct |
122 ms |
46968 KB |
Output is correct |
11 |
Correct |
15 ms |
24068 KB |
Output is correct |
12 |
Correct |
18 ms |
24612 KB |
Output is correct |
13 |
Correct |
30 ms |
26060 KB |
Output is correct |
14 |
Correct |
48 ms |
31384 KB |
Output is correct |
15 |
Correct |
123 ms |
46840 KB |
Output is correct |
16 |
Correct |
15 ms |
23756 KB |
Output is correct |
17 |
Correct |
15 ms |
23844 KB |
Output is correct |
18 |
Correct |
20 ms |
24636 KB |
Output is correct |
19 |
Correct |
20 ms |
24316 KB |
Output is correct |
20 |
Correct |
32 ms |
25444 KB |
Output is correct |
21 |
Correct |
15 ms |
23884 KB |
Output is correct |
22 |
Correct |
14 ms |
23756 KB |
Output is correct |
23 |
Correct |
17 ms |
23832 KB |
Output is correct |
24 |
Correct |
15 ms |
23756 KB |
Output is correct |
25 |
Correct |
16 ms |
23772 KB |
Output is correct |
26 |
Correct |
16 ms |
24028 KB |
Output is correct |
27 |
Correct |
18 ms |
24572 KB |
Output is correct |
28 |
Correct |
26 ms |
26444 KB |
Output is correct |
29 |
Correct |
49 ms |
31392 KB |
Output is correct |
30 |
Correct |
122 ms |
47116 KB |
Output is correct |
31 |
Correct |
196 ms |
50968 KB |
Output is correct |
32 |
Correct |
118 ms |
44872 KB |
Output is correct |
33 |
Correct |
182 ms |
60440 KB |
Output is correct |
34 |
Correct |
124 ms |
46660 KB |
Output is correct |
35 |
Correct |
161 ms |
62312 KB |
Output is correct |