Submission #932030

#	Time	Username	Problem	Language	Result	Execution time	Memory
932030		tfgs	Robot (JOI21_ho_t4)	Cpython 3	0 / 100	1610 ms	97580 KiB

Main

from collections import Counter

def solve():
    n, m = map(int, input().split())

    g = [[] for _ in range(n)]
    for _ in range(m):
        u, v, c, p = map(int, input().split())
        u -= 1
        v -= 1
        g[u].append((c, p, v))
        g[v].append((c, p, u))

    uniq = [set() for _ in range(n)]
    for i in range(n):
        cnt = Counter(c for c, p, v in g[i])
        #  print(cnt)
        uniq[i] = {c for c,_ in filter(lambda cn: cn[1] == 1, cnt.most_common())}
    #  print(uniq)

    st = set()
    vis = [0]*n
    def dfs(u):
        vis[u] = 1
        st.add(u)
        for c, p, v in g[u]:
            if not vis[v] and c in uniq[u]:
                dfs(v)
    dfs(0)

    ans = [-1]*n
    changes = 0
    while changes <= m:
        nxt = set()
        for u in st:
            ans[u] = changes
            for c, p, v in g[u]:
                if not vis[v]:
                    nxt.add(v)

        st = set()
        for u in nxt:
            dfs(u)

        changes += 1

    print(ans[n-1])


solve()

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42