Task: | Building Teams |
Sender: | clovis |
Submission time: | 2024-09-11 14:56:21 +0300 |
Language: | Python3 (PyPy3) |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.05 s | details |
#2 | ACCEPTED | 0.05 s | details |
#3 | ACCEPTED | 0.05 s | details |
#4 | ACCEPTED | 0.05 s | details |
#5 | ACCEPTED | 0.05 s | details |
#6 | ACCEPTED | 0.49 s | details |
#7 | ACCEPTED | 0.49 s | details |
#8 | ACCEPTED | 0.49 s | details |
#9 | ACCEPTED | 0.49 s | details |
#10 | WRONG ANSWER | 0.46 s | details |
#11 | ACCEPTED | 0.05 s | details |
#12 | ACCEPTED | 0.05 s | details |
Code
# idea is to use bipartite check. All nodes will have either red or blue colour, denoted by 0 or 1 value. If there are 2 adjacent nodes that have the same colour, means cannot split the pupils into 2 groups so no valid solution # bipartite check # every node should have a colour or value, 0 or 1 # do bfs to visit each node, colour them accordingly, check for same colours # record the neighbours of every pupil so that you can repeat bfs from collections import deque n, m = map(int, input().split()) colourList = [-1] * n pupilFriendList = [[] for i in range(n)] for i in range(m): friend1, friend2 = map(int, input().split()) pupilFriendList[friend1 - 1].append(friend2 - 1) pupilFriendList[friend2 - 1].append(friend1 - 1) # bfs will colour neighbours accordingly and check for same colour and return true or false whether solution valid or not def bfs(i): # using queue q = deque([i]) while q: node = q.popleft() neighbours = pupilFriendList[node] for neighbour in neighbours: if colourList[node] == colourList[neighbour]: # no possible solution return False # not coloured yet elif colourList[neighbour] == -1: # so that always alternate 0 or 1 colourList[neighbour] = 1 - colourList[node] q.append(neighbour) # if iterate through whole graph using bfs and no issues, then return True because groups can be formed from this graph return True flag = True # iterate through every pupil to colour, do bfs and check for same colours for i in range(n): # -1 means not visited yet and also means first node if colourList[i] == -1: # mark it as first node and colour with value 1 colourList[i] = 1 # if no valid solution because this means no groups can be formed and totally no solution if not bfs(i): flag = False print("IMPOSSIBLE") if flag: # print groups for colour in colourList: print(colour + 1, end=" ") print()
Test details
Test 1
Verdict: ACCEPTED
input |
---|
10 20 3 4 8 10 3 7 1 8 ... |
correct output |
---|
1 1 1 2 2 1 2 2 2 1 |
user output |
---|
2 2 2 1 1 2 1 1 1 2 |
Test 2
Verdict: ACCEPTED
input |
---|
10 20 1 3 8 10 2 4 6 8 ... |
correct output |
---|
1 1 2 2 1 1 1 2 1 1 |
user output |
---|
2 2 1 1 2 2 2 1 2 2 |
Test 3
Verdict: ACCEPTED
input |
---|
10 20 7 10 3 10 9 10 2 10 ... |
correct output |
---|
1 2 2 1 1 1 2 1 2 1 |
user output |
---|
2 1 1 2 2 2 1 2 1 2 |
Test 4
Verdict: ACCEPTED
input |
---|
10 20 2 4 2 10 7 10 4 6 ... |
correct output |
---|
1 2 1 1 2 2 2 1 2 1 |
user output |
---|
2 1 2 2 1 1 1 2 1 2 |
Test 5
Verdict: ACCEPTED
input |
---|
10 20 3 5 8 10 9 10 1 8 ... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 6
Verdict: ACCEPTED
input |
---|
100000 200000 47355 96505 90709 92058 735 80715 91802 94265 ... |
correct output |
---|
1 2 2 1 2 1 1 1 2 2 1 2 1 1 1 ... |
user output |
---|
2 1 1 2 1 2 2 2 1 1 2 1 2 2 2 ... Truncated |
Test 7
Verdict: ACCEPTED
input |
---|
100000 200000 59991 95794 95150 96051 78453 94730 90411 95523 ... |
correct output |
---|
1 1 1 2 2 1 1 2 1 2 1 2 2 2 1 ... |
user output |
---|
2 2 2 1 1 2 2 1 2 1 2 1 1 1 2 ... Truncated |
Test 8
Verdict: ACCEPTED
input |
---|
100000 200000 89827 96402 65137 86792 80965 94708 19479 48078 ... |
correct output |
---|
1 2 1 1 2 1 2 2 2 1 2 1 1 2 1 ... |
user output |
---|
2 1 2 2 1 2 1 1 1 2 1 2 2 1 2 ... Truncated |
Test 9
Verdict: ACCEPTED
input |
---|
100000 200000 72952 83723 66197 70052 2949 52160 55753 95651 ... |
correct output |
---|
1 1 2 2 2 1 1 2 2 2 2 2 1 2 1 ... |
user output |
---|
2 2 1 1 1 2 2 1 1 1 1 1 2 1 2 ... Truncated |
Test 10
Verdict: WRONG ANSWER
input |
---|
100000 200000 38942 96755 70049 82663 7746 72732 87819 99029 ... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE IMPOSSIBLE IMPOSSIBLE IMPOSSIBLE IMPOSSIBLE ... Truncated |
Test 11
Verdict: ACCEPTED
input |
---|
5 4 1 2 3 4 4 5 5 3 |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |
Test 12
Verdict: ACCEPTED
input |
---|
4 5 1 2 1 4 2 3 2 4 ... |
correct output |
---|
IMPOSSIBLE |
user output |
---|
IMPOSSIBLE |