135382025-01-08 09:31:54Leventusz09A lehető legkevesebb átszállás (50 pont)cpp17Hibás válasz 37/50300ms1772 KiB
#include <iostream>
#include <vector>

using namespace std;

int main() {
	int N, M;
	cin >> N >> M;

	vector<int> ss(M, -1);  // minimális átszállások száma
	vector<int> ls(M, -1);  // előző index
	vector<int> ind(M, -1); // bemeneti index

	for (int i = 0, a, b; i < N; i++) {
		cin >> a >> b;
		for (int j = a+1; j <= b; j++) {
			if (ss [a - 1] < ss[j - 1] || ss[j - 1] == -1) {
				ss [j - 1] = ss[a - 1] + 1;
				ls [j - 1] = a - 1;
				ind[j - 1] = i;
			}
		}
	}

	cout << ss[M - 1] << "\n";
	vector<int> ol;
	for (int i = M - 1; i != 0; i = ls[i]) ol.push_back(ind[i] + 1);
	
	for (int i = ss[M - 1]; i >= 0; i--) cout << ol[i] << " ";
	cout << endl;

	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base37/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/013ms1588 KiB
3Elfogadva1/11ms316 KiB
4Hibás válasz0/11ms500 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva2/21ms316 KiB
7Elfogadva2/22ms316 KiB
8Elfogadva2/22ms316 KiB
9Elfogadva2/23ms316 KiB
10Elfogadva2/24ms564 KiB
11Elfogadva2/26ms652 KiB
12Elfogadva2/27ms820 KiB
13Elfogadva2/22ms564 KiB
14Elfogadva2/23ms820 KiB
15Elfogadva2/24ms824 KiB
16Elfogadva2/27ms1000 KiB
17Elfogadva2/29ms1424 KiB
18Elfogadva2/210ms1332 KiB
19Elfogadva2/210ms1524 KiB
20Elfogadva2/212ms1580 KiB
21Elfogadva2/213ms1588 KiB
22Elfogadva2/213ms1600 KiB
23Időlimit túllépés0/2300ms1076 KiB
24Időlimit túllépés0/2300ms1332 KiB
25Időlimit túllépés0/2300ms1332 KiB
26Időlimit túllépés0/2300ms1332 KiB
27Időlimit túllépés0/2287ms1332 KiB
28Időlimit túllépés0/2300ms1772 KiB