Submission #19,112

19112

2025-11-24 19:24:15

pypy3

Time limit exceeded 65/80

1.103s

34700 KiB

class Ter:
    def __init__(self,Nev,Latni,Hossz,Honnan):
        self.Nev = Nev
        self.Latni = Latni
        self.Hossz = Hossz
        self.Honnan = Honnan
        pass
    def kiir(self):
        return print(self.Nev,self.Latni,self.Hossz,self.Honnan)
    
N,M = map(int,input().split())
L = list(map(int,input().split()))
Bit = [Ter(0,0,0,0)]
for i in range(1,N+1):
    Bit.append(Ter(i,L[i-1],L[i-1],0))
Utak = {}
for _ in range(M):
    A,B = map(int,input().split())
    if A not in Utak:
        Utak[A] = [B]
    else:
        Utak[A].append(B)
sor = [Bit[1]]
maxhossz = 0
while len(sor) != 0:
    AktTer = sor.pop()
    if AktTer.Nev == N:
        if AktTer.Hossz > maxhossz:
            maxhossz = AktTer.Hossz
            honnan = AktTer.Honnan
            utvonal = str(AktTer.Nev)
            while honnan != 0:
                utvonal = str(honnan) + " " + utvonal
                honnan = Bit[honnan].Honnan
    if AktTer.Nev in Utak:
        for Hova in Utak[AktTer.Nev]:
            if Bit[Hova].Hossz < AktTer.Hossz + Bit[Hova].Latni:
                Bit[Hova].Hossz = AktTer.Hossz + Bit[Hova].Latni
                Bit[Hova].Honnan = AktTer.Nev
                sor.append(Bit[Hova])
if maxhossz != 0:
    print(maxhossz)
    print(utvonal)
else:
    print(-1)

Subtask		Sum	Test	Verdict	Time	Memory
	subtask1	0/0
	subtask1	0/0	1	Accepted	39ms	19692 KiB
	subtask2	20/20
			2	Accepted	39ms	19692 KiB
			3	Accepted	45ms	19640 KiB
			4	Accepted	45ms	19712 KiB
			5	Accepted	104ms	24080 KiB
			6	Accepted	93ms	23500 KiB
			7	Accepted	130ms	24328 KiB
			8	Accepted	104ms	24040 KiB
			9	Accepted	43ms	21228 KiB
			10	Accepted	119ms	27256 KiB
			11	Accepted	43ms	21040 KiB
			12	Accepted	39ms	19872 KiB
	subtask3	25/25
			13	Accepted	43ms	19664 KiB
			14	Accepted	45ms	19624 KiB
			15	Accepted	41ms	19712 KiB
			16	Accepted	48ms	21160 KiB
			17	Accepted	48ms	19920 KiB
			18	Accepted	50ms	21196 KiB
			19	Accepted	45ms	21208 KiB
			20	Accepted	43ms	21072 KiB
			21	Accepted	41ms	19840 KiB
			22	Accepted	101ms	22248 KiB
			23	Accepted	59ms	21936 KiB
			24	Accepted	103ms	22220 KiB
			25	Accepted	86ms	22052 KiB
			26	Accepted	79ms	22716 KiB
			27	Accepted	82ms	22728 KiB
			28	Accepted	160ms	25140 KiB
			29	Accepted	101ms	23268 KiB
			30	Accepted	128ms	25188 KiB
			31	Accepted	93ms	23780 KiB
			32	Accepted	118ms	24296 KiB
			33	Accepted	86ms	25316 KiB
	subtask4	20/20
			34	Accepted	39ms	19680 KiB
			35	Accepted	43ms	19776 KiB
			36	Accepted	46ms	19608 KiB
			37	Accepted	39ms	19664 KiB
			38	Accepted	52ms	21248 KiB
			39	Accepted	46ms	19712 KiB
			40	Accepted	46ms	21216 KiB
			41	Accepted	43ms	21036 KiB
			42	Accepted	43ms	21200 KiB
			43	Accepted	45ms	19692 KiB
			44	Accepted	46ms	21184 KiB
			45	Accepted	48ms	19688 KiB
			46	Accepted	59ms	21372 KiB
			47	Accepted	46ms	21188 KiB
			48	Accepted	52ms	21140 KiB
			49	Accepted	59ms	21548 KiB
			50	Accepted	46ms	19692 KiB
			51	Accepted	39ms	19828 KiB
			52	Accepted	39ms	19656 KiB
			53	Accepted	45ms	19692 KiB
			54	Accepted	39ms	19692 KiB
			55	Accepted	45ms	19692 KiB
			56	Accepted	39ms	20008 KiB
			57	Accepted	45ms	19692 KiB
			58	Accepted	48ms	19792 KiB
			59	Accepted	46ms	19880 KiB
			60	Accepted	43ms	19600 KiB
			61	Accepted	39ms	19640 KiB
			62	Accepted	46ms	19948 KiB
			63	Accepted	41ms	19828 KiB
			64	Accepted	39ms	19872 KiB
			65	Accepted	45ms	19696 KiB
			66	Accepted	50ms	21228 KiB
	subtask5	0/15
			67	Accepted	39ms	19680 KiB
			68	Accepted	39ms	19692 KiB
			69	Accepted	45ms	19640 KiB
			70	Accepted	45ms	19712 KiB
			71	Accepted	104ms	24080 KiB
			72	Accepted	93ms	23500 KiB
			73	Accepted	130ms	24328 KiB
			74	Accepted	104ms	24040 KiB
			75	Accepted	43ms	21228 KiB
			76	Accepted	119ms	27256 KiB
			77	Accepted	43ms	21040 KiB
			78	Accepted	39ms	19872 KiB
			79	Accepted	43ms	19664 KiB
			80	Accepted	45ms	19624 KiB
			81	Accepted	41ms	19712 KiB
			82	Accepted	48ms	21160 KiB
			83	Accepted	48ms	19920 KiB
			84	Accepted	50ms	21196 KiB
			85	Accepted	45ms	21208 KiB
			86	Accepted	43ms	21072 KiB
			87	Accepted	41ms	19840 KiB
			88	Accepted	101ms	22248 KiB
			89	Accepted	59ms	21936 KiB
			90	Accepted	103ms	22220 KiB
			91	Accepted	86ms	22052 KiB
			92	Accepted	79ms	22716 KiB
			93	Accepted	82ms	22728 KiB
			94	Accepted	160ms	25140 KiB
			95	Accepted	101ms	23268 KiB
			96	Accepted	128ms	25188 KiB
			97	Accepted	93ms	23780 KiB
			98	Accepted	118ms	24296 KiB
			99	Accepted	86ms	25316 KiB
			100	Accepted	43ms	19776 KiB
			101	Accepted	46ms	19608 KiB
			102	Accepted	39ms	19664 KiB
			103	Accepted	52ms	21248 KiB
			104	Accepted	46ms	19712 KiB
			105	Accepted	46ms	21216 KiB
			106	Accepted	43ms	21036 KiB
			107	Accepted	43ms	21200 KiB
			108	Accepted	45ms	19692 KiB
			109	Accepted	46ms	21184 KiB
			110	Accepted	48ms	19688 KiB
			111	Accepted	59ms	21372 KiB
			112	Accepted	46ms	21188 KiB
			113	Accepted	52ms	21140 KiB
			114	Accepted	59ms	21548 KiB
			115	Accepted	46ms	19692 KiB
			116	Accepted	39ms	19828 KiB
			117	Accepted	39ms	19656 KiB
			118	Accepted	45ms	19692 KiB
			119	Accepted	39ms	19692 KiB
			120	Accepted	45ms	19692 KiB
			121	Accepted	39ms	20008 KiB
			122	Accepted	45ms	19692 KiB
			123	Accepted	48ms	19792 KiB
			124	Accepted	46ms	19880 KiB
			125	Accepted	43ms	19600 KiB
			126	Accepted	39ms	19640 KiB
			127	Accepted	46ms	19948 KiB
			128	Accepted	41ms	19828 KiB
			129	Accepted	39ms	19872 KiB
130	Accepted		45ms	19696 KiB
131	Accepted		50ms	21228 KiB
132	Accepted		108ms	22448 KiB
133	Accepted		64ms	21980 KiB
134	Accepted		90ms	22160 KiB
135	Accepted		85ms	22180 KiB
136	Accepted		98ms	22144 KiB
137	Accepted		93ms	21988 KiB
138	Accepted		96ms	22212 KiB
139	Accepted		78ms	22816 KiB
140	Accepted		105ms	23796 KiB
141	Accepted		100ms	23268 KiB
142	Accepted		115ms	24648 KiB
143	Accepted		112ms	24620 KiB
144	Accepted		111ms	26144 KiB
145	Accepted		122ms	24456 KiB
146	Accepted		135ms	28284 KiB
147	Accepted		412ms	31252 KiB
148	Time limit exceeded		1.085s	32744 KiB
149	Time limit exceeded		1.103s	34700 KiB