oj.uz

Submission #719652

# Submission time Handle Problem Language Result Execution time Memory
719652 2023-04-06T12:53:20 Z Arturgo Parking (CEOI22_parking) C++14
20 / 100
 180 ms 19804 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;
	
	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]
		&& 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()) {
			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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 17544 KB Output is correct
2 Correct 174 ms 19496 KB Output is correct
3 Correct 106 ms 14688 KB Output is correct
4 Correct 88 ms 14084 KB Output is correct
5 Correct 180 ms 19804 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 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 340 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 2 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 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 452 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 448 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Incorrect 1 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 176 ms 17544 KB Output is correct
12 Correct 174 ms 19496 KB Output is correct
13 Correct 106 ms 14688 KB Output is correct
14 Correct 88 ms 14084 KB Output is correct
15 Correct 180 ms 19804 KB Output is correct
16 Incorrect 1 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -