# Untitled

unknown

plain_text

7 months ago

4.6 kB

13

Indexable

Never

^{}

Pink and Blue Xenny was a teacher and he had N students. The N children were sitting in a room. Each child was wearing a white T-shirt, with a unique number from the range 1 to N written on it. T-Shirts of pink and blue color were to be distributed among the students by Xenny. This made the students very happy. Xenny felt that a random distribution of T-Shirts would be very uninteresting. So, he decided to keep an interesting condition: Every student would get a T-Shirt that is of a different color than his/her friends. That is, if X and Y are friends and X has a Pink T-Shirt, then Y should compulsorily have a Blue T-Shirt, and vice-versa. Also, Xenny had a belief that Boys should wear blue T-Shirts and Girls should wear pink T-Shirts. If a boy was given a pink T-Shirt or a girl was given a Blue T-Shirt, he called it an inversion. So, Xenny wanted to distribute T-Shirts in the above-mentioned interesting manner and also wanted to minimize "inversions". Help him solve the task. Note: There are no disjoint groups of friends in the room. That is, 2 distinct groups with finite number of students do not exist, but exactly 1 group of students exists in the given situation. Input The first line is the number of test cases T. First line of each test case contains 2 space-separated integers - N and M - number of students and number of friendships present respectively. Second line consists of N space-separated characters, where ith character denotes the gender of the ith student. B: Boy, G: Girl. M lines follow. Each line consists of 2 space-separated integers, u and v, showing that u is a friend of v and vice-versa. Output If Xenny could distribute the T-Shirts in the desired way, print the minimum number of inversions required. Else, print -1. Constraints 1 ≤ N ≤ 105 1 ≤ M ≤ 105 1 ≤ u, v ≤ N Colors of T-Shirt are represented by uppercase characters 'B' and 'G' Sample Input 3 3 2 B G B 1 2 1 3 6 9 B B B G G G 3 5 2 6 4 2 6 3 3 1 3 4 6 1 5 1 1 4 6 5 G G G B G G 6 3 1 3 2 3 4 3 5 3 Output 1 -1 2 Explanation #1 Student 1 can be given a Blue T-Shirt. Hence, Student 2 and 3 would receive Pink T-Shirts. Since, Student 3 is a Boy and has received a Pink T-Shirt, number of inversions = 1. #include <iostream> using namespace std; void Init(); void Solve(); int main(void) { // freopen("input.txt", "r", stdin); int T; cin >> T; for (int i = 1; i <= T; i += 1) { Init(); Solve(); } return 0; } int N, M; int ListLen[100006]; int mListLen[100006]; int mColor[100006]; int Color[100006]; int **List; int Edges[100006][2]; void Init() { cin >> N >> M; for (int i = 1; i <= N; i += 1) { ListLen[i] = 0; mListLen[i] = 0; mColor[i] = -1; } List = new int * [N + 1]; char IN; for (int i = 1; i <= N; i += 1) { cin >> IN; Color[i] = (IN == 'B') ? 1 : 0; } int u, v; for (int i = 0; i < M; i += 1) { cin >> u >> v; Edges[i][0] = u; Edges[i][1] = v; mListLen[u] += 1; mListLen[v] += 1; } for (int i = 1; i <= N; i += 1) { List[i] = new int[mListLen[i]]; } for (int i = 0; i < M; i += 1) { u = Edges[i][0]; v = Edges[i][1]; ListLen[u] += 1; ListLen[v] += 1; List[u][ListLen[u]] = v; List[v][ListLen[v]] = u; } } int BFS(); void Solve() { mColor[1] = Color[1]; int res1 = BFS(); int res2 = N - res1; if (res1 > res2) { cout << res2 << endl; } else { cout << res1 << endl; } } int Queue[10000001]; int FrontQ, RearQ; void PushQ(int); int PopQ(); bool Visited[100006]; int BFS() { for (int i = 1; i <= N; i += 1) Visited[i] = 0; FrontQ = RearQ = -1; PushQ(1); Visited[1] = 1; int cnt = 0; while (FrontQ != RearQ) { int u = PopQ(); for (int i = 1; i <= ListLen[u]; i += 1) { int v = List[u][i]; if (!Visited[v]) { Visited[v] = 1; mColor[v] = 1 - mColor[u]; if (mColor[v] != Color[v]) cnt += 1; PushQ(v); } else { if (mColor[v] == mColor[u]) return -1; } } } return cnt; } void PushQ(int x) { RearQ += 1; Queue[RearQ] = x; } int PopQ() { FrontQ += 1; return Queue[FrontQ]; }

Leave a Comment