Submission #462595

#	Time	Username	Problem	Language	Result	Execution time	Memory
462595		AdamGS	T-Covering (eJOI19_covering)	C++14	0 / 100	75 ms	95140 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}, n, m, F[LIM], mi[LIM], ok[LIM];
int dx[]={0, 1, 0, -1}, dy[]={1, 0, -1, 0};
vector<int>T[LIM], czy_srodek[LIM], ile_wolnych[LIM], uzyte[LIM];
queue<pair<int,int>>q;
void zmien(int i, int j) {
	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);
	cin >> n >> m;
	rep(i, n) rep(j, m) {
		T[i].pb(0);
		czy_srodek[i].pb(0);
		uzyte[i].pb(0);
		ile_wolnych[i].pb(INF);
	}
	rep(i, n) rep(j, m) cin >> T[i][j];
	int k;
	cin >> k;
	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=i+d[b];
			}
		}
		if(ile_sasiadow==0) continue;
		if(ile_sasiadow>1) {
			cout << "No\n";
			return 0;
		}
		rep(a, 4) if(0<=i+dx[a] && i+dx[a]<n && 0<=j+dy[a] && j+dy[a]<m) {
			zmien(i+dx[a], j+dy[a]);
		}
		zmien(i, j);
	}
	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;
		}
		rep(a, 4) if(0<=i+dx[a] && i+dx[a]<n && 0<=j+dy[a] && j+dy[a]<m) {
			zmien(i+dx[a], j+dy[a]);
		}
	}
	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);
		}
		if(j+2<m && czy_srodek[i][j+2]) {
			uni(i*m+j, i*m+j+2);
		}
	}
	rep(i, n) rep(j, m) if(czy_srodek[i][j] && !uzyte[i][j]) {
		zmien(i, j);
		rep(a, 4) if(0<=i+dx[a] && i+dx[a]<n && 0<=j+dy[a] && j+dy[a]<m) {
			zmien(i+dx[a], j+dy[a]);
		}
	}
	int sum=0;
	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")
      | 
covering.cpp: In function 'int main()':
covering.cpp:63:7: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   63 |   int x=-1, y=-1;
      |       ^
covering.cpp:63:13: warning: variable 'y' set but not used [-Wunused-but-set-variable]
   63 |   int x=-1, y=-1;
      |             ^

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