oj.uz

Submission #932030

# Submission time Handle Problem Language Result Execution time Memory
932030 2024-02-22T20:28:27 Z tfgs Robot (JOI21_ho_t4) Python 3
0 / 100
 1610 ms 97580 KB 
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.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3420 KB Output is correct
2 Correct 13 ms 3192 KB Output is correct
3 Incorrect 13 ms 3420 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 33288 KB Output is correct
2 Correct 202 ms 18420 KB Output is correct
3 Correct 773 ms 44944 KB Output is correct
4 Correct 325 ms 26300 KB Output is correct
5 Incorrect 1610 ms 97580 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3420 KB Output is correct
2 Correct 13 ms 3192 KB Output is correct
3 Incorrect 13 ms 3420 KB Output isn't correct
4 Halted 0 ms 0 KB -