oj.uz

Submission #719649

# Submission time Handle Problem Language Result Execution time Memory
719649 2023-04-06T12:38:36 Z Arturgo Parking (CEOI22_parking) C++14
10 / 100
 193 ms 19436 KB 
#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()) {
			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;
	
	for(int iPlace = 0;iPlace < nbPlaces;iPlace++) {
		if(voitures[iPlace].size() == 1) {
			aTraiter.push_back(iPlace);
			explore(voitures[iPlace].back());
		}
	}
	
	for(int iCouleur = 0;iCouleur < nbCouleurs;iCouleur++) {
		if(!estPasse[iCouleur]
		&& voitures[positions[iCouleur][0]].size() == 2
		&& voitures[positions[iCouleur][1]].size() == 2
		&& voitures[positions[iCouleur][0]][1] == iCouleur
		&& voitures[positions[iCouleur][1]][1] == iCouleur) {
			branchements.push_back(iCouleur);
		}
	}
	
	reverse(branchements.begin(), branchements.end());
	
	while(true) {
		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);
				}
			}
		}
		
		if(branchements.empty()) break;
		
		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);
		}
	}
	
	cout << solution.size() << "\n";
	
	for(pair<int, int> dep : solution) {
		cout << 1 + dep.first << " " << 1 + dep.second << "\n";
	}
		
	return 0;
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 17104 KB Output is correct
2 Correct 172 ms 19304 KB Output is correct
3 Correct 129 ms 14420 KB Output is correct
4 Correct 88 ms 14228 KB Output is correct
5 Correct 193 ms 19436 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -