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:00:25
2016-05-28 13:39:35
2016-05-28 13:09:34
Task:Graph painting
Sender:Verto
Submission time:2016-05-28 13:09:34
Status:READY
Result:TIME LIMIT EXCEEDED

Show test data

Code

import sys
def asints(s):
	return [int(x.strip()) for x in s.split()]
def asoneint(s):
	return int(s.strip())
lines = sys.stdin.readlines()


class Node:
	def __init__(self, name):
		self.name = name
		self.neighbors = []
		self.color = None
	def connect(self, other):
		self.neighbors.append(other)
		other.neighbors.append(self)
	def debug(self):
		print "{}: {}".format(self.name, [x.name for x in self.neighbors])

t = asoneint(lines[0])
linei = 1
for testi in range(t):
	nodes = {}
	n, m = asints(lines[linei])
	linei += 1
	for i in range(1, n+1):
		nodes[i] = Node(i)
	for i in range(m):
		a, b = asints(lines[linei])
		linei += 1
		nodes[a].connect(nodes[b])
	#for node in nodes.values():
	#	node.debug()
	#print
	for node in nodes.values():
		n_red = 0
		n_blue = 0
		for neigh in node.neighbors:
			if neigh.color is None:
				continue
			elif neigh.color == 'R':
				n_red += 1
			else:
				n_blue += 1
		if n_red > n_blue:
			node.color = 'B'
		else:
			node.color = 'R'
	for node in sorted(nodes.values(), key=lambda x:x.name):
		print node.color,
	print