Dyrektor patrzy – Omówienie zadania – Preorder / Postorder, wykorzystanie DFS

Dyrektor patrzy – Omówienie zadania – Preorder / Postorder, wykorzystanie DFS

Szczegółowe omówienie zadania Dyrektor patrzy:

Link do powyższego omówienia zadania Dyrektor patrzy: https://youtu.be/R4FOYOblSNE?t=1755
Omówienie kodu który zadania Dyrektor patrzy: https://youtu.be/R4FOYOblSNE?t=4104

Link do treści zadania Dyrektor patrzy i możliwości umieszczania rozwiązań:
https://szkopul.edu.pl/problemset/problem/NeHsbwV_Rok4bVgn9LjDoZR9/site

Zadanie Dyrektor patrzy pokazuje zastosowanie techniki Preorder / Postorder: https://youtu.be/R4FOYOblSNE?t=2901
Preorder/postorder pozwala na sprawdzenie zależności między wierzchołkami: https://youtu.be/R4FOYOblSNE?t=3515
Jak zrobić nasze zadanie korzystając z Preorder/Postorder? https://youtu.be/R4FOYOblSNE?t=3780
Złożoność rozwiązania z Preorder / Postorder:
https://youtu.be/R4FOYOblSNE?t=3937
Implementacja Preorder / Postorder w kodzie programu:
https://youtu.be/R4FOYOblSNE?t=4571

Technika Preorder / Postorder korzysta z algorytmu DFS: https://youtu.be/P4xemLnkDFc?t=1243
DFS jest przewidywalny i rozwiązuje nasz problem: https://youtu.be/R4FOYOblSNE?t=2743

Rozwiązanie brutalne – zamiast Preorder / Postorder: https://youtu.be/R4FOYOblSNE?t=2490


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

Lista zadań z rozwiązaniami: https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad: https://oki.org.pl/tutorial/

Zajęcia: https://oki.org.pl/harmonogram-zajec/
Informacje o zajęciach: https://oki.org.pl/newsletter.php

Warto startować w Olimpiadzie Informatycznej!
https://youtu.be/K7fZfJ8nN6A?t=109


Kod C++ programu Dyrektor patrzy, który jest omówiony w powyższym filmie i który otrzymuje 100%


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

const int MAXN = 5e5 + 7;

vector<int> G[MAXN];
int pre[MAXN];
int post[MAXN];
int c = 1;

void DFS(int v, int p)
{
	pre[v] = c;
	++c;
	for (auto u : G[v]) {
		if (u != p)
			DFS(u, v);
	}
	post[v] = c;
	++c;
}

// czy a jest przodkiem b?
bool czy_przodek(int a, int b)
{
	return (pre[a] < pre[b]) && (post[a] > post[b]);
}

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

	int n, q;
	cin >> n >> q;
	for (int i = 2; i <= n; ++i) {
		int p;
		cin >> p;
		G[i].push_back(p);
		G[p].push_back(i);
	}

	DFS(1, 1);

	for (int i = 1; i <= q; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		bool ca = czy_przodek(c, a);
		bool cb = czy_przodek(c, b);
		if (ca && cb)
			cout << "Dyrektor patrzy\n";
		else if (ca)
			cout << "Tylko B\n";
		else if (cb)
			cout << "Tylko A\n";
		else
			cout << "Droga wolna\n";
	}
	return 0;
}
Kod C++ programu Dyrektor patrzy, który jest omówiony w powyższym filmie i który otrzymuje 100%

 


Kod Python programu Cyclic Components, który otrzymuje 100%:

from sys import setrecursionlimit
setrecursionlimit(500000)

c = 1
def DFS(v, p, G, pre, post):
	global c
	pre[v] = c
	c += 1
	for u in G[v]:
		if (u != p):
			DFS(u, v, G, pre, post)
	post[v] = c
	c += 1

def czy_przodek(a, b, pre, post):
	return (pre[a] < pre[b]) and (post[a] > post[b])

def solve():
	n, q = map(int, input().split())
	G = [[] for i in range(n + 1)]
	parrent = list(map(int, input().split()))
	for i in range(n-1):
		G[parrent[i]].append(i + 2)
		G[i + 2].append(parrent[i])

	pre = [0] * (n + 1)
	post = [0] * (n + 1)
	DFS(1, 1, G, pre, post)

	for i in range(q):
		a, b, c = map(int, input().split())
		ca = czy_przodek(c, a, pre, post)
		cb = czy_przodek(c, b, pre, post)
		if (ca and cb):
			print("Dyrektor patrzy")
		elif (ca):
			print("Tylko B")
		elif (cb):
			print("Tylko A")
		else:
			print("Droga wolna")

solve()

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz