Submission #719662

#	Time	Username	Problem	Language	Result	Execution time	Memory
719662		Arturgo	Parking (CEOI22_parking)	C++14	100 / 100	1167 ms	33684 KiB

Main

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> voitures;

vector<int> libres;
vector<vector<int>> positions;

vector<pair<int, int>> solution;

bool solve(int couleur) {
	if(positions[couleur][0] == positions[couleur][1])
		return false;
	
	if(voitures[positions[couleur][0]].size() == 2
	&& voitures[positions[couleur][1]].size() == 2
	&& voitures[positions[couleur][0]][1] == couleur
	&& voitures[positions[couleur][1]][1] == couleur) {
		// Branchement sortant
		
		if(libres.empty()) {
			cerr << "NOPE" << endl;
			cout << -1 << endl;
			exit(0);
		}
		
		int libre = libres.back();
		libres.pop_back();
		
		solution.push_back({positions[couleur][0], libre});
		solution.push_back({positions[couleur][1], libre});
			
		voitures[positions[couleur][0]].pop_back();
		voitures[positions[couleur][1]].pop_back();
		positions[couleur] = {libre, libre};
		voitures[libre] = {couleur, couleur};
		return true;
	}
	
	if(voitures[positions[couleur][0]].size() == 2
	&& voitures[positions[couleur][0]][1] == couleur) {
		if(voitures[positions[couleur][1]].size() != 1) return false;
		
		solution.push_back({
			positions[couleur][0], 
			positions[couleur][1]
		});
	
		voitures[positions[couleur][0]].pop_back();	
		positions[couleur] = {
			positions[couleur][1], 
			positions[couleur][1]
		};
		voitures[positions[couleur][0]] = {couleur, couleur};
		return true;
	}
	
	if(voitures[positions[couleur][0]].size() != 1) return false;
	if(voitures[positions[couleur][1]].back() != couleur) return false;
	
	voitures[positions[couleur][1]].pop_back();
	
	if(voitures[positions[couleur][1]].empty())
		libres.push_back(positions[couleur][1]);
	
	solution.push_back({
		positions[couleur][1],
		positions[couleur][0]
	});
	positions[couleur] = {
		positions[couleur][0],
		positions[couleur][0]
	};
	voitures[positions[couleur][0]] = {couleur, couleur};
	return true;
}

vector<int> branchements;
vector<bool> estPasse;

void explore(int couleur, int der = -1) {
	if(estPasse[couleur]) return;
	estPasse[couleur] = true;
	
	vector<int> ps = positions[couleur];
	
	if(voitures[positions[couleur][0]].size() == 2
	&& voitures[positions[couleur][1]].size() == 2
	&& voitures[positions[couleur][0]][1] == couleur
	&& voitures[positions[couleur][1]][1] == couleur) {
		branchements.push_back(couleur);
	}
	
	vector<int> couls1 = voitures[positions[couleur][0]];
	vector<int> couls2 = voitures[positions[couleur][1]];
	
	for(int val : couls2) couls1.push_back(val);
	
	for(int val : couls1) {
		if(val != couleur && val != der) {
			explore(val, couleur);
			return;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int nbCouleurs, nbPlaces;
	cin >> nbCouleurs >> nbPlaces;
	
	voitures.resize(nbPlaces);
	positions.resize(nbCouleurs);
	estPasse = vector<bool>(nbCouleurs, false);
	
	for(int iPlace = 0;iPlace < nbPlaces;iPlace++) {
		int a, b;
		cin >> a >> b;
		
		if(a != 0) {
			voitures[iPlace].push_back(a - 1);
			positions[a - 1].push_back(iPlace);
		}
		
		if(b != 0) {
			voitures[iPlace].push_back(b - 1);
			positions[b - 1].push_back(iPlace);
		}
		
		if(voitures[iPlace].empty()) {
			libres.push_back(iPlace);
		}
	}
	
	vector<int> aTraiter;
	
	vector<int> toSolve;
	
	for(int iPlace = 0;iPlace < nbPlaces;iPlace++) {
		toSolve.push_back(iPlace);
		if(voitures[iPlace].size() == 1) {
			aTraiter.push_back(iPlace);
			explore(voitures[iPlace].back());
		}
	}
	
	for(int iCouleur = 0;iCouleur < nbCouleurs;iCouleur++) {
		if(!estPasse[iCouleur]) {
			explore(iCouleur, -1);
		}
	}
	
	reverse(branchements.begin(), branchements.end());
	
	while(true) {
		cerr << libres.size() << endl;
		while(!aTraiter.empty()) {
			int place = aTraiter.back();
			aTraiter.pop_back();
			
			vector<int> ps = positions[voitures[place].back()];
			if(solve(voitures[place].back())) {	
				for(int pos : ps) {
					if(voitures[pos].size() == 1) aTraiter.push_back(pos);
				}
			}
		}
		
		/*for(pair<int, int> sol : solution) {
			cerr << 2 + sol.first << " " << 2 + sol.second << endl;
		}*/
		
		if(!branchements.empty()) {
			//cerr << "BRANCHE" << endl;
			int couleur = branchements.back();
			branchements.pop_back();
			
			vector<int> ps = positions[couleur];
			solve(couleur);
			
			for(int pos : ps) {
				if(voitures[pos].size() == 1) aTraiter.push_back(pos);
			}
		}
		else if(!toSolve.empty()) {
			int place = toSolve.back();
			toSolve.pop_back();
			
			if(voitures[place].size() < 2) continue;
			if(voitures[place][0] == voitures[place][1]) continue;
			if(libres.empty()) {
				cout << -1 << endl;
				exit(0);
			}
			
			int libre = libres.back();
			libres.pop_back();
			
			solution.push_back({place, libre});
			
			for(int& pos : positions[voitures[place][1]]) {
				if(pos == place) pos = libre;
			}
			
			voitures[libre].push_back(voitures[place][1]);
			voitures[place].pop_back();
						
			aTraiter.push_back(place);
		}
		else {
			break;
		}
	}
	
	cout << solution.size() << "\n";
	
	for(pair<int, int> dep : solution) {
		cout << 1 + dep.first << " " << 1 + dep.second << "\n";
	}
		
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15
• Subtask 5: 25 / 25
• Subtask 6: 15 / 15