Jumbo – Omówienie zadania

Jumbo – Omówienie zadania

Szczegółowe omówienie zadania Jumbo:

Link do powyższego omówienia zadania Jumbo:
https://youtu.be/I_Dr_vEnt2A?t=2950

Link do treści zadania Jumbo:
https://ki.staszic.waw.pl/task.php?name=jumbo

——-
Zadanie Jumbo pokazuje technikę preorder i postorder w drzewie:
https://youtu.be/I_Dr_vEnt2A?t=3560
——-

Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz:
https://youtu.be/pkLXuuOe_qA?t=3625

——-

Zadanie omawia Michał Szeliga – laureat Olimpiady Informatycznej Juniorów:
https://youtu.be/OA8BeVFvaNU?t=830

——-

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> sas[100000];
int pre[100000];
int post[100000];
bool vis[100000]; //Czy odwiedzony?
int krzykniecie = 0;

void DFS(int v){
	vis[v] = 1;
	pre[v] = ++krzykniecie; //Zwiększ krzyknięcie o 1, ustaw pre[v] na krzyknięcie
	for (int u : sas[v]){
		if (vis[u] == false){
			DFS(u);
		}
	}
	post[v] = ++krzykniecie;	
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for (int i = 1; i < n; i++){
		int ojciec;
		cin>>ojciec;
		sas[ojciec].push_back(i);
		sas[i].push_back(ojciec);
	}
	DFS(0);
	while (true){
		int a,b;
		cin>>a;
		if (a == -1) return 0;
		cin>>b;
		if (pre[a] < pre[b] && post[a] > post[b]) cout<<"TAK\n";
		else cout<<"NIE\n";
	}
}
Kod C++ programu Jumbo, który jest omówiony w powyższym filmie i który otrzymuje 100%
=============

Kod C++ Darii, uczestniczki naszych zajęć, który otrzymuje 100%:

Bardzo dziękuję za pomoc w trakcie zajęć!

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

const int MAX_N = 1e5 + 6;
vector idole[MAX_N];
int preOrder[MAX_N];
int postOrder[MAX_N];
bool odwiedzone[MAX_N];
int pre = 0;
int post = 0;

void DFS(int start) {
    pre++;
    preOrder[start] = pre;
    odwiedzone[start] = true;
    for (int i : idole[start]) {
        if (!odwiedzone[i]) {
            DFS(i);
            post++;
        }
    }
    postOrder[start] = post;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    int a, b;
    cin >> n;
    int idol;
    for (int i = 1; i < n; ++i) { cin >> idol;
        idole[idol].push_back(i);
    }
    DFS(0);

 
    while (true) {
        cin >> a;
        if (a == -1) {
            break;
        }
        cin >> b;
        if (preOrder[a] < preOrder[b] && postOrder[a] > postOrder[b]) {
            cout << "TAK" << "\n";
        } else {
            cout << "NIE" << "\n";
        }
    }

    return 0;
}

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz