Rezultati

Up. imeNalogaJezikRezultatČas oddaje
jayzcrew-2018 Dolenjec Python 3 0/100Prekoračen čas (TLE) 10. maj '18 @ 19:27

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 9,289 MiB 0,000 s OK
#2 0/3 9,262 MiB 0,000 s Napačen odgovor
Tvoj izhod:
​DA
<<<EOF>>>
Pravilen izhod:
​NE
<<<EOF>>>
#3 0/3 9,340 MiB 0,000 s Napačen odgovor
Tvoj izhod:
​DA
<<<EOF>>>
Pravilen izhod:
​NE
<<<EOF>>>
#4 3/3 9,363 MiB 0,000 s OK
#5 3/3 9,426 MiB 0,000 s OK
#6 3/3 9,270 MiB 0,000 s OK
#7 3/3 9,340 MiB 0,000 s OK
#8 3/3 9,426 MiB 0,000 s OK
#9 3/3 9,375 MiB 0,000 s OK
#10 3/3 9,266 MiB 0,000 s OK
#11 3/3 9,430 MiB 0,000 s OK
#12 3/3 9,340 MiB 0,000 s OK
#13 3/3 9,363 MiB 0,000 s OK
#14 3/3 9,273 MiB 0,000 s OK
#15 3/3 9,445 MiB 0,000 s OK
#16 3/3 9,441 MiB 0,000 s OK
#17 3/3 9,277 MiB 0,000 s OK
#18 3/3 9,535 MiB 0,000 s OK
#19 3/3 9,367 MiB 0,000 s OK
#20 3/3 9,523 MiB 0,000 s OK
#21 3/3 9,434 MiB 0,000 s OK
#22 3/3 9,734 MiB 0,000 s OK
#23 0/3 57,227 MiB 2,380 s Prekoračen čas
#24 0/3 53,504 MiB 2,384 s Prekoračen čas
#25 0/3 47,715 MiB 2,340 s Prekoračen čas
#26 3/3 31,477 MiB 1,177 s OK
#27 3/3 25,734 MiB 0,940 s OK
#28 0/3 48,547 MiB 2,833 s Prekoračen čas
#29 0/3 49,164 MiB 2,249 s Prekoračen čas
#30 3/3 29,625 MiB 1,127 s OK
#31 3/3 25,754 MiB 0,981 s OK
#32 3/3 21,168 MiB 0,571 s OK
#33 0/4 9,445 MiB 0,000 s Napačen odgovor
Tvoj izhod:
​DA
<<<EOF>>>
Pravilen izhod:
​NE
<<<EOF>>>

Ocenjevani program (dolenc.py):
from collections import deque
import sys

def Nothing(u,v):
    return True

def DFS(G, roots = None, previsit = Nothing, postvisit = Nothing):
    s = deque()
    n = len(G)
    visitet = [False] * n
    if roots == None:
        roots = range(n)
    v, it = None, iter(roots)
    while True:
        try:
            u = next(it)
        except StopIteration:
            if v is None:
                return True
            u = v
            v, it = s.pop()
            if not postvisit(u,v):
                return False
        if visitet[u]:
            continue
        visitet[u] = True
        if not previsit(u,v):
            return False
        s.append((v,it))
        v, it = u, iter(G[u])


def revers(G):
    n = len(G)
    V = [[] for i in range(n)]
    for i in range(n):
        for j in G[i]:
            V[j].append(i)
    return V

def decompose(G,q0):
    n = len(G)
    R = revers(G)
    post = []
    def postord(u, v):
        post.append(u)
        return True
    DFS(R, previsit = postord)
    l = [None] * n
    M = []
    c = 0
    comp = []
    zac = None
    def previsit(u,v):
        nonlocal zac
        if v is None:
            comp.append([])
            M.append(set())
        l[u] = c
        comp[c].append(u)
        if u == q0:
            zac = c
        return True
    def postvis(u,v):
        nonlocal c
        for w in G[u]:
            if l[w] != c:
                M[c].add(l[w])
        if v is None:
            c += 1
        return True
    DFS(G, reversed(post), previsit, postvis)
    return (comp, [list(s) for s in M], zac)

line = sys.stdin.readline()
line = line.strip().split()

nn,mm,dd,qq = int(line[0]),int(line[1]),int(line[2]),int(line[3])
line = sys.stdin.readline()
QQ = list(map(lambda i: i-1,map(int,line.strip().split())))
Q0 = QQ[0]
fff = set(QQ)



majosaminase = set()

Graf = [[] for _ in range(nn)]

for _ in range(mm):
    odc = sys.stdin.readline().strip().split()
    a,b = int(odc[0])-1,int(odc[1])-1
    if a == b:
        if a in fff:
            majosaminase.add(a)
    Graf[a].append(b)


komponenta, graf, zac = decompose(Graf,Q0)

def previsitfin(u, v=None):
    if len(komponenta[u]) > 1:
        for i in komponenta[u]:
            if i in fff:
                print("DA")
                sys.exit(0)
    elif len(komponenta[u]) == 1:
        if komponenta[u][0] in majosaminase:
            print("DA")
            sys.exit(0)
    return True

DFS(graf, roots=[zac], previsit=previsitfin)
print("NE")