Submission #9576566


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from operator import itemgetter
from collections import defaultdict

N,M = map(int,readline().split())
D = [0] + list(map(int,readline().split()))
m = map(int,read().split())
UV = list(zip(m,m))

graph = [[] for _ in range(N+1)]
for u,v in UV:
    graph[u].append((v,D[v]))
    graph[v].append((u,D[u]))

subgraph = [[] for _ in range(N+1)]
is_ng = False
for v in range(1,N+1):
    graph[v].sort(key = itemgetter(1))
    w,d = graph[v][0]
    if D[v] < d:
        is_ng = True
        break
    subgraph[w].append(v)

if is_ng:
    print(-1)
    exit()

INF = 10 ** 9
wt_edge = defaultdict(lambda:INF)
color = [0] * (N+1)

# (index, weight), sorted by wt
I = sorted(enumerate(D), key = itemgetter(1))[1:]

for v, wt in I:
    if color[v]:
        continue
    stack = [v]
    color[v] = 1
    v0 = v
    while stack:
        v = stack.pop()
        cw = 3 - color[v]
        for w in subgraph[v]:
            if w == v0:
                continue
            color[w] = cw
            wt_edge[(v,w)] = D[w]
            wt_edge[(w,v)] = D[w]
            stack.append(w)

S = ''.join('B' if x == 1 else 'W' for x in color[1:])
C = [wt_edge[(u,v)] for u,v in UV]

print(S)
print('\n'.join(map(str,C)))

Submission Info

Submission Time
Task E - Bichromization
User maspy
Language Python (3.4.3)
Score 900
Code Size 1374 Byte
Status AC
Exec Time 1672 ms
Memory 147044 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 3
AC × 43
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt
All 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 03-07.txt, 03-08.txt, 03-09.txt, 03-10.txt, 04-01.txt, 04-02.txt, 04-03.txt, 04-04.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 26 ms 3584 KB
01-02.txt AC 21 ms 3364 KB
01-03.txt AC 22 ms 3356 KB
01-04.txt AC 21 ms 3360 KB
01-05.txt AC 21 ms 3360 KB
01-06.txt AC 22 ms 3360 KB
01-07.txt AC 22 ms 3364 KB
01-08.txt AC 22 ms 3356 KB
01-09.txt AC 22 ms 3356 KB
01-10.txt AC 22 ms 3360 KB
02-01.txt AC 1490 ms 145060 KB
02-02.txt AC 1650 ms 145636 KB
02-03.txt AC 1584 ms 145408 KB
02-04.txt AC 1672 ms 145388 KB
02-05.txt AC 138 ms 22064 KB
02-06.txt AC 144 ms 22072 KB
02-07.txt AC 152 ms 22072 KB
02-08.txt AC 1599 ms 146568 KB
02-09.txt AC 143 ms 22244 KB
02-10.txt AC 144 ms 22244 KB
02-11.txt AC 651 ms 80584 KB
02-12.txt AC 71 ms 13752 KB
02-13.txt AC 74 ms 13760 KB
02-14.txt AC 658 ms 80276 KB
02-15.txt AC 133 ms 22244 KB
02-16.txt AC 1620 ms 147044 KB
03-01.txt AC 83 ms 12704 KB
03-02.txt AC 84 ms 12844 KB
03-03.txt AC 1162 ms 103508 KB
03-04.txt AC 1227 ms 105896 KB
03-05.txt AC 1249 ms 105140 KB
03-06.txt AC 1237 ms 104816 KB
03-07.txt AC 42 ms 8220 KB
03-08.txt AC 406 ms 52520 KB
03-09.txt AC 1212 ms 104836 KB
03-10.txt AC 414 ms 52460 KB
04-01.txt AC 625 ms 91076 KB
04-02.txt AC 611 ms 91196 KB
04-03.txt AC 396 ms 49720 KB
04-04.txt AC 325 ms 49708 KB
sample-01.txt AC 22 ms 3364 KB
sample-02.txt AC 22 ms 3364 KB
sample-03.txt AC 21 ms 3356 KB