Submission #19,111

19111

2025-11-24 18:43:56

pypy3

Time limit exceeded 20/80

1.103s

29416 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())
    Utak.append([A,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
    for ut in Utak:
        if ut[0] == AktTer.Nev and Bit[ut[1]].Hossz < AktTer.Hossz + Bit[ut[1]].Latni:
            Bit[ut[1]].Hossz = AktTer.Hossz + Bit[ut[1]].Latni
            Bit[ut[1]].Honnan = AktTer.Nev
            sor.append(Bit[ut[1]])
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	0/20
			2	Accepted	41ms	19692 KiB
			3	Accepted	45ms	19692 KiB
			4	Accepted	41ms	19652 KiB
			5	Accepted	234ms	23992 KiB
			6	Accepted	119ms	23288 KiB
			7	Accepted	493ms	24036 KiB
			8	Accepted	474ms	24176 KiB
			9	Accepted	52ms	21480 KiB
			10	Time limit exceeded	1.085s	26344 KiB
			11	Accepted	54ms	21476 KiB
			12	Accepted	45ms	19692 KiB
	subtask3	0/25
			13	Accepted	43ms	19668 KiB
			14	Accepted	46ms	19572 KiB
			15	Accepted	39ms	19664 KiB
			16	Accepted	52ms	21420 KiB
			17	Accepted	46ms	19644 KiB
			18	Accepted	56ms	21428 KiB
			19	Accepted	45ms	21236 KiB
			20	Accepted	43ms	21228 KiB
			21	Accepted	45ms	19736 KiB
			22	Accepted	663ms	22636 KiB
			23	Accepted	64ms	21980 KiB
			24	Accepted	451ms	22752 KiB
			25	Accepted	123ms	22504 KiB
			26	Accepted	86ms	22760 KiB
			27	Accepted	90ms	23016 KiB
			28	Time limit exceeded	1.082s	27876 KiB
			29	Accepted	143ms	23780 KiB
			30	Time limit exceeded	1.082s	27880 KiB
			31	Accepted	93ms	25068 KiB
			32	Accepted	112ms	29416 KiB
			33	Accepted	86ms	25832 KiB
	subtask4	20/20
			34	Accepted	39ms	19664 KiB
			35	Accepted	43ms	19796 KiB
			36	Accepted	39ms	19860 KiB
			37	Accepted	45ms	19684 KiB
			38	Accepted	59ms	21392 KiB
			39	Accepted	45ms	19652 KiB
			40	Accepted	52ms	21464 KiB
			41	Accepted	43ms	21220 KiB
			42	Accepted	45ms	21080 KiB
			43	Accepted	46ms	19704 KiB
			44	Accepted	64ms	21736 KiB
			45	Accepted	39ms	19752 KiB
			46	Accepted	57ms	21776 KiB
			47	Accepted	50ms	21356 KiB
			48	Accepted	46ms	21068 KiB
			49	Accepted	68ms	21532 KiB
			50	Accepted	39ms	19700 KiB
			51	Accepted	45ms	19764 KiB
			52	Accepted	39ms	19684 KiB
			53	Accepted	46ms	19600 KiB
			54	Accepted	39ms	19744 KiB
			55	Accepted	39ms	19692 KiB
			56	Accepted	46ms	19896 KiB
			57	Accepted	45ms	19776 KiB
			58	Accepted	48ms	21436 KiB
			59	Accepted	46ms	21312 KiB
			60	Accepted	45ms	19604 KiB
			61	Accepted	45ms	19632 KiB
			62	Accepted	54ms	21432 KiB
			63	Accepted	45ms	19776 KiB
			64	Accepted	41ms	19956 KiB
			65	Accepted	39ms	19680 KiB
			66	Accepted	48ms	21380 KiB
	subtask5	0/15
			67	Accepted	39ms	19664 KiB
			68	Accepted	41ms	19692 KiB
			69	Accepted	45ms	19692 KiB
			70	Accepted	41ms	19652 KiB
			71	Accepted	234ms	23992 KiB
			72	Accepted	119ms	23288 KiB
			73	Accepted	493ms	24036 KiB
			74	Accepted	474ms	24176 KiB
			75	Accepted	52ms	21480 KiB
			76	Time limit exceeded	1.085s	26344 KiB
			77	Accepted	54ms	21476 KiB
			78	Accepted	45ms	19692 KiB
			79	Accepted	43ms	19668 KiB
			80	Accepted	46ms	19572 KiB
			81	Accepted	39ms	19664 KiB
			82	Accepted	52ms	21420 KiB
			83	Accepted	46ms	19644 KiB
			84	Accepted	56ms	21428 KiB
			85	Accepted	45ms	21236 KiB
			86	Accepted	43ms	21228 KiB
			87	Accepted	45ms	19736 KiB
			88	Accepted	663ms	22636 KiB
			89	Accepted	64ms	21980 KiB
			90	Accepted	451ms	22752 KiB
			91	Accepted	123ms	22504 KiB
			92	Accepted	86ms	22760 KiB
			93	Accepted	90ms	23016 KiB
			94	Time limit exceeded	1.082s	27876 KiB
			95	Accepted	143ms	23780 KiB
			96	Time limit exceeded	1.082s	27880 KiB
			97	Accepted	93ms	25068 KiB
			98	Accepted	112ms	29416 KiB
			99	Accepted	86ms	25832 KiB
			100	Accepted	43ms	19796 KiB
			101	Accepted	39ms	19860 KiB
			102	Accepted	45ms	19684 KiB
			103	Accepted	59ms	21392 KiB
			104	Accepted	45ms	19652 KiB
			105	Accepted	52ms	21464 KiB
			106	Accepted	43ms	21220 KiB
			107	Accepted	45ms	21080 KiB
			108	Accepted	46ms	19704 KiB
			109	Accepted	64ms	21736 KiB
			110	Accepted	39ms	19752 KiB
			111	Accepted	57ms	21776 KiB
			112	Accepted	50ms	21356 KiB
			113	Accepted	46ms	21068 KiB
			114	Accepted	68ms	21532 KiB
			115	Accepted	39ms	19700 KiB
			116	Accepted	45ms	19764 KiB
			117	Accepted	39ms	19684 KiB
			118	Accepted	46ms	19600 KiB
			119	Accepted	39ms	19744 KiB
			120	Accepted	39ms	19692 KiB
			121	Accepted	46ms	19896 KiB
			122	Accepted	45ms	19776 KiB
			123	Accepted	48ms	21436 KiB
			124	Accepted	46ms	21312 KiB
			125	Accepted	45ms	19604 KiB
			126	Accepted	45ms	19632 KiB
			127	Accepted	54ms	21432 KiB
			128	Accepted	45ms	19776 KiB
			129	Accepted	41ms	19956 KiB
130	Accepted		39ms	19680 KiB
131	Accepted		48ms	21380 KiB
132	Accepted		563ms	22680 KiB
133	Accepted		64ms	21844 KiB
134	Accepted		374ms	22496 KiB
135	Accepted		112ms	22248 KiB
136	Accepted		204ms	22392 KiB
137	Accepted		111ms	21988 KiB
138	Accepted		416ms	22788 KiB
139	Accepted		94ms	23016 KiB
140	Accepted		238ms	23784 KiB
141	Accepted		141ms	23272 KiB
142	Accepted		702ms	24292 KiB
143	Time limit exceeded		1.103s	24296 KiB
144	Accepted		888ms	24772 KiB
145	Accepted		771ms	24296 KiB
146	Time limit exceeded		1.093s	27364 KiB
147	Time limit exceeded		1.082s	27112 KiB
148	Time limit exceeded		1.087s	25576 KiB
149	Time limit exceeded		1.087s	24556 KiB