Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2576
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2576
Reversing Arrows
By Dâmi Henrique, INATEL 
Brasil
Timelimit: 2
Bibi and Bibika are playing a simple game where the judge, with each round, makes a drawing with several circles and arrows linking some of them.
Bibi must count the least X number of arrows that need to be inverted to exist at least one path from A to B and Bibika must count the smallest amount Y of inverted arrows to exist at least one path in the opposite direction from B to A. The game who find the lowest value. If there is no path between A > B or B > A, the game ends in a draw, regardless of the number of arrows reversed.
As the judge in some rounds makes a very large drawing, it is quite complicated to check the veracity of the answers given by the girls. Your task is to automate this process for him.
Input
The first line of each test case contains four integers C ( 1 ≤ C ≤ 104 ) , S ( 0 ≤ S ≤ 5 x 105), A e B, ( 1 ≤ A, B ≤ C ), where C is the number of circles, S is the number of arrows, A and B are the ends of the game. Each of the next S lines contain two integers C1 and C2, representing an arrow connecting the circle C1 to the circle C2.
Output
For each test case, display the winner's name and the amount Q inverted arrows in Bibi format: Q or Bibika: Q. If the game ends in a draw, display Bibibibika.
| Input Samples | Output Samples |
|
6 7 1 5 |
Bibika: 1 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#include <deque>
#include <vector>
#define MAXN 10010
using namespace std;
typedef pair < int, int> ii;
int processado1[MAXN], processado2[MAXN], pai[MAXN], peso[MAXN];
vector<int> grafo[MAXN], transposto[MAXN];
int bibi, bibika;
int find(int x) {
if (x == pai[x]) return x;
return pai[x] = find(pai[x]);
}
void join(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (peso[x] < peso[y]) {
pai[x] = y;
} else if (peso[x] > peso[y]) {
pai[y] = x;
} else {
pai[x] = y;
peso[y]++;
}
}
int main() {
int c, s, a, b;
scanf("%d %d %d %d", &c, &s, &a, &b);
while (s--) {
int u, v;
scanf("%d %d", &u, &v);
join(u, v);
grafo[u].push_back(v);
transposto[v].push_back(u);
}
if (find(a) != find(b)) {
printf("Bibibibika\n");
return 0;
}
deque < ii> fila1, fila2;
fila1.push_back(ii(0, a));
while (!fila1.empty()) {
ii davez = fila1.front();
fila1.pop_front();
int v = davez.second, dist = davez.first;
if (processado1[v]) continue;
processado1[v] = 1;
if (v == b) {
bibi = dist;
break;
}
for (int u : grafo[v]) {
if (!processado1[u]) fila1.push_front(ii(dist, u));
}
for (int u : transposto[v]) {
if (!processado1[u]) fila1.push_back(ii(dist + 1, u));
}
}
fila2.push_back(ii(0, b));
while (!fila2.empty()) {
ii davez = fila2.front();
fila2.pop_front();
int v = davez.second, dist = davez.first;
if (processado2[v]) continue;
processado2[v] = 1;
if (v == a) {
bibika = dist;
break;
}
for (int u : grafo[v]) {
if (!processado2[u]) fila2.push_front(ii(dist, u));
}
for (int u : transposto[v]) {
if (!processado2[u]) fila2.push_back(ii(dist + 1, u));
}
}
if (bibi < bibika) {
printf("Bibi: %d\n", bibi);
} else if (bibi > bibika) {
printf("Bibika: %d\n", bibika);
} else {
printf("Bibibibika\n");
}
return 0;
}
Input
1
1 6
3 2
4 2
4 6
5 4
5 3
Output