oj.uz

Submission #971513

# Submission time Handle Problem Language Result Execution time Memory
971513 2024-04-28T17:32:19 Z Lcc735 Railway (BOI17_railway) Python 3
0 / 100
 1000 ms 45248 KB 
n,m,k=map(int,input().split())
caminos=[]
pedido=[]
nodos=[]
ady=[]
for i in range(n):
    nodos.append([])
    ady.append([])
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1 
    b-=1
    caminos.append([a,b])
    pedido.append(0)
    nodos[a].append(i)
    ady[a].append(b)
    nodos[b].append(i)
    ady[b].append(a)




def llegar(a,b,pasado,soli,nodo,adyac):
    for i in range(len(adyac)):
        c=adyac[i]
        if(c==b):
            soli.add(nodo[i])
            return True
        else:
            if(c not in pasado):
                pasado.add(c)
                if (llegar(c,b,pasado,soli,nodos[c],ady[c])):
                    pasado.add(c)
                    soli.add(nodo[i])
                    return True

        


for i in range(m):
    soli=set()
    s=input().split()
    for i in range(1,len(s)-1):
        a=int(s[i])-1
        b=int(s[i+1])-1
        pasado=set()
        pasado.add(a)
        llegar(a,b,pasado,soli,nodos[a],ady[a])
    for i in soli:
        pedido[i]+=1

ok=[]
for i in range(len(pedido)):
    if(pedido[i]>=k):
        ok.append(i)
        
print(len(ok))
for i in ok:
    print(i+1,end=' ')
print('')

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2908 KB Output is correct
2 Execution timed out 1018 ms 7764 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2908 KB Output is correct
2 Execution timed out 1018 ms 7764 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 382 ms 45076 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 418 ms 45248 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 418 ms 45248 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2908 KB Output is correct
2 Execution timed out 1018 ms 7764 KB Time limit exceeded
3 Halted 0 ms 0 KB -