Submission #463612

#	Time	Username	Problem	Language	Result	Execution time	Memory
463612		AdamGS	T-Covering (eJOI19_covering)	C++14	100 / 100	196 ms	62312 KiB

covering

#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 (stderr)

covering.cpp:2: warning: ignoring '#pragma GCC option' [-Wunknown-pragmas]
    2 | #pragma GCC option("arch=native","tune=native","no-zero-upper")
      |

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 30 / 30