Closing the Farm – Omówienie zadania z Amerykańskiej Olimpiady Informatycznej USACO – poziom Gold

Closing the Farm – Omówienie zadania z Amerykańskiej Olimpiady Informatycznej USACO – poziom Gold

Szczegółowe omówienie zadania Closing the Farm:

Link do powyższego omówienia zadania Closing the Farm:
https://youtu.be/P2sLFZBjOmM?t=2608

Link do treści zadania Closing the Farm:
http://www.usaco.org/index.php?page=viewproblem2&cpid=646

——
Zadanie Closing the Farm jest zadaniem pokazującym zastosowanie algorytmu Find And Union (FAU):
https://youtu.be/P2sLFZBjOmM?t=1432

—–
Zadanie Closing the Farm pochodzi z dywizji GOLD Amerykańskiej Olimpiady Informatycznej USACO – odpowiednika naszej Olimpiady Informatycznej Licealistów
Daje piękny wpis do CV:
https://youtu.be/P2sLFZBjOmM?t=7223

———-
Link do wszystkich zadań z tej edycji konkursu USACO:
http://www.usaco.org/index.php?page=open16results

Dlaczego warto brać udział w Amerykańskiej Olimpiady Informatycznej USACO?
https://youtu.be/K7fZfJ8nN6A?t=6848
——–
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
——-

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

const int MAX_BARNS = 2e5+7; //2e5 = 2*10^5
int rep[MAX_BARNS];
vector<int> graph[MAX_BARNS];
int closing_order[MAX_BARNS];
bool is_barn_built[MAX_BARNS];
int answer[MAX_BARNS];

int Find (int a) {
 if(rep[a]==a)
    return a;

 rep[a] = Find ( rep[a] );
 return ( rep[a] );
}

void Union (int a, int b) {
 rep[Find(a)]=rep[Find(b)];
}


int main(){
 freopen("closing.in", "r", stdin);
 freopen("closing.out", "w", stdout);

 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);

 int number_of_barns, number_of_connections;
 int barn_a, barn_b;
 int groups_of_barns;
 int i, j, act_closing, act_barn, target_barn, edge;
 int node; 

 cin >> number_of_barns >> number_of_connections;
 for (i=1; i<=number_of_connections; ++i) {
    cin >> barn_a >> barn_b;
    graph[barn_a].push_back(barn_b);
    graph[barn_b].push_back(barn_a);
 } 
////   /*Writing out the graph*/ 
//// for (node=1; node<=number_of_farms; ++node) {
////    cout << node << ": ";
////    for (edge=0; edge<graph[node].size(); ++edge) { 
////       cout << graph[node][edge] << " ";
////    } 
////    cout << "\n";
//// } 
 
 for (i=1; i<=number_of_barns; ++i) {
    cin >> closing_order[i];
 }

 for (i=1; i<=number_of_barns; ++i) {
    rep[i] = i;
 }
 
 groups_of_barns = 0;
 for (act_closing=number_of_barns; act_closing>=1; --act_closing) {
    ++groups_of_barns;
    act_barn = closing_order[act_closing];
    is_barn_built[act_barn] = true;
    for (edge=0; edge<graph[act_barn].size(); ++edge) {
       target_barn = graph[act_barn][edge];
	   if ( is_barn_built[target_barn] == false ) 
          continue;
       if ( Find (act_barn) == Find (target_barn) )
	      continue;
//mamy innego rep ni stodoa do ktorej powadzi droga
	   Union (act_barn, target_barn);
	   --groups_of_barns;
	}
	if (groups_of_barns == 1)
	   answer[act_closing] = 1;
	else 
	   answer[act_closing] = 0;
 }
 
 for (act_closing=1; act_closing<=number_of_barns; ++act_closing) {
	if (answer[act_closing]  == 1)
	   cout << "YES" << "\n";
	else
	   cout << "NO" << "\n";
 } 
 
 return 0;
}
Kod C++ programu Closing the Farm, który jest omówiony w powyższym filmie i który otrzymuje 100%

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz