Submission #464510

#	Time	Username	Problem	Language	Result	Execution time	Memory
464510		RaresFelix	T-Covering (eJOI19_covering)	C++17	25 / 100	276 ms	54724 KiB

covering

#include <bits/stdc++.h>
#define MN 1077171
#define INF 1271717171
#define ACI
using namespace std;
typedef pair<int, int> ii;
int n, m, k, rez;
struct tetr {
	int l, c, id, activ = 1;
	vector<int> Vec; // vecini
} Te[MN];

vector<vector<int> > A; //valori
vector<vector<int> > B; //centre
vector<vector<int> > O; //obstacole
//ifstream fi("a.in");
//ofstream fo("a.out");

void not_okay() {
	cout << "No\n";
	exit(0);
}
void adiac_lin() {
	int DX[] = {0, -1, 0, 1, -1, 0, 1, 0};
	int DY[] = {-1, 0, 0, 0, 1, 1, 1, 2};
	int ln, cn;
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j < m; ++j) {
			if(B[i][j] && B[i][j+1]){
				for(int d = 0; d < 8; ++d){
					ln = i + DX[d];
					cn = j + DY[d];
					if(ln < 1 || cn < 1 || ln > n || cn > m || O[ln][cn]) not_okay();
					O[ln][cn] = 1;
					rez += A[ln][cn];
				}
				B[i][j] = B[i][j+1] = 0;
			}
		}
}
void adiac_col() {
	int DX[] = {0, 1, -1, 0, 1, 2, 0, 1};
	int DY[] = {-1, -1, 0, 0, 0, 0, 1, 1};
	int ln, cn;
	for(int i = 1; i < n; ++i)
		for(int j = 1; j <= m; ++j) {
			if(B[i][j] && B[i+1][j]){
				for(int d = 0; d < 8; ++d){
					ln = i + DX[d];
					cn = j + DY[d];
					if(ln < 1 || cn < 1 || ln > n || cn > m || O[ln][cn]) not_okay();
					O[ln][cn] = 1;
					rez += A[ln][cn];
				}
				B[i][j] = B[i+1][j] = 0;
			}
		}
}
void adiac_diagpr() {
	int DX[] = {0, -1, 0, 1, 0, 1, 2, 1};
	int DY[] = {-1, 0, 0, 0, 1, 1, 1, 2};
	int ln, cn;
	for(int i = 1; i < n; ++i)
		for(int j = 1; j < m; ++j) {
			if(B[i][j] && B[i+1][j+1]){
				for(int d = 0; d < 8; ++d){
					ln = i + DX[d];
					cn = j + DY[d];
					if(ln < 1 || cn < 1 || ln > n || cn > m || O[ln][cn]) not_okay();
					O[ln][cn] = 1;
					rez += A[ln][cn];
				}
				B[i][j] = B[i+1][j+1] = 0;
			}
		}
}
void adiac_diagsec() {
	int DX[] = {-1, 0, 0, 0, 1, 1, 1, 2};
	int DY[] = {0, -1, 0, 1, -2, -1, 0, -1};
	int ln, cn;
	for(int i = 1; i < n; ++i)
		for(int j = 2; j < m; ++j) {
			if(B[i][j] && B[i+1][j-1]){
				for(int d = 0; d < 8; ++d){
					ln = i + DX[d];
					cn = j + DY[d];
					if(ln < 1 || cn < 1 || ln > n || cn > m || O[ln][cn]) not_okay();
					O[ln][cn] = 1;
					rez += A[ln][cn];
				}
				B[i][j] = B[i+1][j-1] = 0;
			}
		}
}

void obligat() {
	int DX[] = {-1, 0, 1, 0};
	int DY[] = {0, 1, 0, -1};
	int ln, cn, nr;
	for(int i = 1; i < n; ++i)
		for(int j = 2; j < m; ++j) {
			if(B[i][j]) {
				nr = 0;
				for(int d = 0; d < 4; ++d){
					ln = i + DX[d];
					cn = j + DY[d];
					nr += (ln < 1 || cn < 1 || ln > n || cn > m || O[ln][cn]);
				}
				if(!nr)continue;
				if(nr > 1) not_okay();
				///pur si simplu evitam obstacolul
				for(int d = 0; d < 4; ++d){
					ln = i + DX[d];
					cn = j + DY[d];
					if(ln < 1 || cn < 1 || ln > n || cn > m || O[ln][cn]) continue;
					O[ln][cn] = 1;
					rez += A[ln][cn];
				}
			}
		}
}
map<pair<int, int>, int> Tetro;

void vecini() {
	for(int i = 1; i <= k; ++i) {
		if(!B[Te[i].l][Te[i].c]) Te[i].activ = 0;
		else Tetro[{Te[i].l, Te[i].c}] = Te[i].id;
	}
	int DX[] = {-2, 0, 2, 0};
	int DY[] = {0, 2, 0, -2};
	int ln, cn, nr;
	for(int i = 1; i <= k; ++i){
		if(!Te[i].activ)continue;
		for(int d = 0; d < 4; ++d){
			ln = Te[i].l + DX[d];
			cn = Te[i].c + DY[d];
			if(ln < 1 || cn < 1 || ln > n || cn > m || O[ln][cn]) continue;
			if(Tetro[{ln, cn}]) Te[i].Vec.push_back(Tetro[{ln, cn}]);
		}
	}
}

vector<vector<int> > Componente;
int Viz[MN];

void dfs(int u) {
	if(Viz[u])return;
	Viz[u] = 1;
	Componente.back().push_back(u);
	for(auto it : Te[u].Vec) dfs(it);
}

void desparte_comp() {
	///vom despartii valorile ramase in componente conexe pe care le vom rezolva individual
	//(acum oricare doua tetromino-uri sunt la distanta >= 2, \
		daca nu sunt pe aceasi linie nu se influenteaza)
	for(int i = 1; i <= k; ++i){
		if(!Te[i].activ || Viz[i])continue;
		Componente.push_back({});
		dfs(i);
	}
}

int blocat(int i) {
	int DX[] = {-1, 0, 1, 0};
	int DY[] = {0, 1, 0, -1};
	int ln, cn, nr = 0;
	for(int d = 0; d < 4; ++d){
		ln = Te[i].l + DX[d];
		cn = Te[i].c + DY[d];
		if(ln < 1 || cn < 1 || ln > n || cn > m || O[ln][cn]) ++nr;
	}
	if(nr > 1) not_okay();
	return nr;
}
void repara(int i) {
	int DX[] = {-1, 0, 1, 0, 0};
	int DY[] = {0, 1, 0, -1, 0};
	int ln, cn, nr;
	nr = 0;
	for(int d = 0; d < 5; ++d){
		ln = Te[i].l + DX[d];
		cn = Te[i].c + DY[d];
		nr += (ln < 1 || cn < 1 || ln > n || cn > m || O[ln][cn]);
	}
	if(nr > 1) not_okay();
	///pur si simplu evitam obstacolul
	for(int d = 0; d < 5; ++d){
		ln = Te[i].l + DX[d];
		cn = Te[i].c + DY[d];
		if(ln < 1 || cn < 1 || ln > n || cn > m || O[ln][cn]) continue;
		O[ln][cn] = 1;
		rez += A[ln][cn];
	}
}

int Reparat[MN];
void afis_O() {
	#ifndef AICI
	return;
	#endif // AICI
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
			cout << O[i][j] << " \n"[j==m];
	cout << "\n";
}
void dfs2(int u) {
	afis_O();
	if(Reparat[u])return;
	Reparat[u] = 1;
	repara(u);
	for(auto it : Te[u].Vec)
		dfs2(it);
}

int minimul(int i) {
	int DX[] = {-1, 0, 1, 0};
	int DY[] = {0, 1, 0, -1};
	int ln, cn, nr;
	nr = INF;
	for(int d = 0; d < 4; ++d){
		ln = Te[i].l + DX[d];
		cn = Te[i].c + DY[d];
		nr = min(nr, A[ln][cn]);
	}
	return nr;
}

void repara_fortat(int i, int val) {
	int DX[] = {-1, 0, 1, 0, 0};
	int DY[] = {0, 1, 0, -1, 0};
	int ln, cn;
	for(int d = 0; d < 5; ++d){
		ln = Te[i].l + DX[d];
		cn = Te[i].c + DY[d];
	}
	///pur si simplu evitam obstacolul
	for(int d = 0; d < 5; ++d){
		ln = Te[i].l + DX[d];
		cn = Te[i].c + DY[d];
		if(A[ln][cn] == val && d != 5){
			 val = -INF;
			 continue;
		}
		O[ln][cn] = 1;
		rez += A[ln][cn];
	}
}

void repara_fortat_special(int i, int lc, int cc) {
	int DX[] = {-1, 0, 1, 0, 0};
	int DY[] = {0, 1, 0, -1, 0};
	int ln, cn;
	for(int d = 0; d < 5; ++d){
		ln = Te[i].l + DX[d];
		cn = Te[i].c + DY[d];
	}
	///pur si simplu evitam obstacolul
	for(int d = 0; d < 5; ++d){
		ln = Te[i].l + DX[d];
		cn = Te[i].c + DY[d];
		if(ln == lc && cn == cc) continue;
		O[ln][cn] = 1;
		rez += A[ln][cn];
	}
}

int are_circ = 0;
int V3[MN];

void dfs3(int nod) {
	if(V3[nod] == 1){
		are_circ = nod;
		return;
	}
	if(V3[nod] == 2) return;
	V3[nod] = 1;
	for(auto it : Te[nod].Vec) dfs3(it);
	V3[nod] = 2;
}

bool circuit(int com) {
	are_circ = 0;
	for(auto it : Componente[com]) V3[it] = 0;
	dfs3(Componente[com].back());
	return are_circ;
}

void process_comp(int nr) {
	//va procesa componenta nr si va adauga suma la rezultat
	for(auto it : Componente[nr]){
		if(blocat(it)) {
			dfs2(it);
			return;
		}
	}
	if(!circuit(nr)) {
		// e corect peste tot, trebuie gasit minimul, reparat si adaptat sirul...
		int vmi = INF, pmi = 0, tmp;
		for(auto it : Componente[nr]){
			tmp = minimul(it);
			if(tmp < vmi){
				vmi = tmp;
				pmi = it;
			}
		}
		repara_fortat(pmi, vmi);
		Reparat[pmi] = 1;
		for(auto it : Te[pmi].Vec)
			dfs2(it);
	} else {
		/// pur si simplu vom incerca sa reparam unul dintre tetrominou-urile din \
			circuit catre vecin, restul se vor pune in loc
		int nod = are_circ; ///trebuie orientat catre unul dintre vecini, altfel este scos(nu prea conteaza care)
		int vec = Te[nod].Vec.back();
		int lc, cc;
		lc = (Te[nod].l + Te[vec].l) / 2;
		cc = (Te[nod].c + Te[vec].c) / 2;
		repara_fortat_special(nod, lc, cc);
		Reparat[nod] = 1;
		dfs2(Te[nod].Vec[0]);
	}
}

int main(){
	cin >> n >> m;
	A.assign(n+2, vector<int>(m+2));
	B.assign(n+2, vector<int>(m+2));
	O.assign(n+2, vector<int>(m+2));
	for(int i = 0; i <= n; ++i)
		O[i][0] = O[i][m+1] = 1;
	for(int i = 0; i <= m; ++i)
		O[0][i] = O[n+1][i] = 1;
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
			cin >> A[i][j];
	cin >> k;
	for(int i = 1; i <= k; ++i){
		cin >> Te[i].l >> Te[i].c;
		++Te[i].l;
		++Te[i].c;
		B[Te[i].l][Te[i].c] = 1;
		Te[i].id = i;
	}
	///vom rezolva cazurile speciale de adiacenta inainte de a trece mai departe
	adiac_lin();
	adiac_col();
	adiac_diagpr();
	adiac_diagsec();
	//gaseste vecini
	vecini();
	//componente
	desparte_comp();
	//pentru fiecare componenta, o vom procesa
	for(int i = 0; i < Componente.size(); ++i)
		process_comp(i);
	afis_O();
	cout << rez << "\n";
    return 0;
}

Compilation message (stderr)

covering.cpp:155:2: warning: multi-line comment [-Wcomment]
  155 |  //(acum oricare doua tetromino-uri sunt la distanta >= 2, \
      |  ^
covering.cpp:312:3: warning: multi-line comment [-Wcomment]
  312 |   /// pur si simplu vom incerca sa reparam unul dintre tetrominou-urile din \
      |   ^
covering.cpp: In function 'void vecini()':
covering.cpp:131:14: warning: unused variable 'nr' [-Wunused-variable]
  131 |  int ln, cn, nr;
      |              ^~
covering.cpp: In function 'int main()':
covering.cpp:355:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  355 |  for(int i = 0; i < Componente.size(); ++i)
      |                 ~~^~~~~~~~~~~~~~~~~~~

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