Code Submission Evaluation System Login

CSES - HIIT Open 2016

HIIT Open 2016

Contest start:2016-05-28 11:00:00
Contest end:2016-05-28 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard | Statistics


History
2016-05-28 15:36:43
Task:Graph painting
Sender:LTR
Submission time:2016-05-28 15:36:43
Status:READY
Result:WRONG ANSWER

Show test data

Code

#include <iostream>
#include <vector>
#include <cstdio>

int main()
{
	int t;
	std::cin >> t;
	for (int ti = 0; ti < t; ++ti) {
		int n, m;
		std::cin >> n >> m;
		std::vector<std::vector<int>> E(n);
		std::vector<bool> visited(n, false);
		std::vector<bool> red(n, false);
		for (int mi = 0; mi < m; ++mi) {
			int a, b;
			std::cin >> a >> b;
			a--;
			b--;
			E[a].push_back(b);
			E[b].push_back(a);
		}

		std::vector<int> A;
		std::vector<int> B;
		
		int i0 = 0;
		bool isred = false;
		A.push_back(i0);
		while (i0 < n) {
			while (!A.empty()) {
				B.clear();
				for (int a : A) {
					red[a] = isred;
					visited[a] = true;
					for (int aa : E[a]) {
						if (!visited[aa])
							B.push_back(aa);
					}
				}
				A.swap(B);
				isred = !isred;
			}

			++i0;
			while ((i0 < n) && visited[i0]) ++i0;
		}

		for (bool b : red)
			std::cout << (b ? "R" : "B") << " ";
		std::cout << std::endl;
	}
}