Submission #19,109

19109

2025-11-24 16:38:52

pypy3

Time limit exceeded 40/80

1.103s

28904 KiB

N,M = map(int,input().split())
L = list(map(int,input().split()))
Ut = []
Honnan = [0] * (N+1)
for _ in range(M):
    A,B = map(int,input().split())
    Ut.append([A,B])
sor = [[1,L[0]]]
maxhossz = 0
while len(sor) != 0:
    akt = sor.pop()
    aktter = akt[0]
    akthossz = akt[1]
    if aktter == N:
        if akthossz > maxhossz:
            maxhossz = akthossz
            honnan = Honnan[aktter]
            utvonal = [aktter]
            while honnan != 0:
                utvonal.append(honnan)
                honnan = Honnan[honnan]
    for el in Ut:
        if el[0] == aktter:
            sor.append([el[1],akthossz+L[el[1]-1]])
            Honnan[el[1]] = aktter
if maxhossz != 0:
    print(maxhossz)
    for i in range(len(utvonal)-1,-1,-1):
        print(utvonal[i],end=" ")
else:
    print(-1)

Subtask		Sum	Test	Verdict	Time	Memory
	subtask1	0/0
	subtask1	0/0	1	Accepted	39ms	19436 KiB
	subtask2	20/20
			2	Accepted	39ms	19440 KiB
			3	Accepted	43ms	19512 KiB
			4	Accepted	39ms	19424 KiB
			5	Accepted	194ms	23464 KiB
			6	Accepted	109ms	23368 KiB
			7	Accepted	407ms	24036 KiB
			8	Accepted	404ms	24040 KiB
			9	Accepted	54ms	21476 KiB
			10	Accepted	945ms	25320 KiB
			11	Accepted	52ms	21480 KiB
			12	Accepted	45ms	19788 KiB
	subtask3	0/25
			13	Accepted	43ms	19572 KiB
			14	Accepted	43ms	19496 KiB
			15	Accepted	41ms	19628 KiB
			16	Accepted	89ms	21796 KiB
			17	Accepted	41ms	19484 KiB
			18	Accepted	65ms	21632 KiB
			19	Accepted	46ms	19808 KiB
			20	Accepted	41ms	19912 KiB
			21	Accepted	46ms	19692 KiB
			22	Time limit exceeded	1.103s	22384 KiB
			23	Accepted	54ms	21456 KiB
			24	Time limit exceeded	1.103s	22384 KiB
			25	Time limit exceeded	1.083s	22248 KiB
			26	Accepted	75ms	21972 KiB
			27	Accepted	75ms	23012 KiB
			28	Time limit exceeded	1.082s	27880 KiB
			29	Time limit exceeded	1.09s	23828 KiB
			30	Time limit exceeded	1.103s	27880 KiB
			31	Accepted	100ms	24772 KiB
			32	Accepted	120ms	28904 KiB
			33	Accepted	86ms	23560 KiB
	subtask4	20/20
			34	Accepted	41ms	19860 KiB
			35	Accepted	43ms	19604 KiB
			36	Accepted	46ms	19628 KiB
			37	Accepted	39ms	19568 KiB
			38	Accepted	94ms	21652 KiB
			39	Accepted	46ms	19636 KiB
			40	Accepted	64ms	21828 KiB
			41	Accepted	41ms	19808 KiB
			42	Accepted	45ms	19944 KiB
			43	Accepted	39ms	19516 KiB
			44	Accepted	86ms	21844 KiB
			45	Accepted	39ms	19432 KiB
			46	Accepted	695ms	21772 KiB
			47	Accepted	63ms	21476 KiB
			48	Accepted	46ms	21008 KiB
			49	Accepted	64ms	21724 KiB
			50	Accepted	45ms	19436 KiB
			51	Accepted	45ms	19568 KiB
			52	Accepted	39ms	19584 KiB
			53	Accepted	39ms	19588 KiB
			54	Accepted	43ms	19684 KiB
			55	Accepted	39ms	19796 KiB
			56	Accepted	37ms	19712 KiB
			57	Accepted	43ms	19688 KiB
			58	Accepted	46ms	21548 KiB
			59	Accepted	46ms	21480 KiB
			60	Accepted	46ms	19584 KiB
			61	Accepted	39ms	19708 KiB
			62	Accepted	52ms	21584 KiB
			63	Accepted	39ms	19692 KiB
			64	Accepted	46ms	19696 KiB
			65	Accepted	39ms	19616 KiB
			66	Accepted	52ms	21496 KiB
	subtask5	0/15
			67	Accepted	41ms	19860 KiB
			68	Accepted	39ms	19440 KiB
			69	Accepted	43ms	19512 KiB
			70	Accepted	39ms	19424 KiB
			71	Accepted	194ms	23464 KiB
			72	Accepted	109ms	23368 KiB
			73	Accepted	407ms	24036 KiB
			74	Accepted	404ms	24040 KiB
			75	Accepted	54ms	21476 KiB
			76	Accepted	945ms	25320 KiB
			77	Accepted	52ms	21480 KiB
			78	Accepted	45ms	19788 KiB
			79	Accepted	43ms	19572 KiB
			80	Accepted	43ms	19496 KiB
			81	Accepted	41ms	19628 KiB
			82	Accepted	89ms	21796 KiB
			83	Accepted	41ms	19484 KiB
			84	Accepted	65ms	21632 KiB
			85	Accepted	46ms	19808 KiB
			86	Accepted	41ms	19912 KiB
			87	Accepted	46ms	19692 KiB
			88	Time limit exceeded	1.103s	22384 KiB
			89	Accepted	54ms	21456 KiB
			90	Time limit exceeded	1.103s	22384 KiB
			91	Time limit exceeded	1.083s	22248 KiB
			92	Accepted	75ms	21972 KiB
			93	Accepted	75ms	23012 KiB
			94	Time limit exceeded	1.082s	27880 KiB
			95	Time limit exceeded	1.09s	23828 KiB
			96	Time limit exceeded	1.103s	27880 KiB
			97	Accepted	100ms	24772 KiB
			98	Accepted	120ms	28904 KiB
			99	Accepted	86ms	23560 KiB
			100	Accepted	43ms	19604 KiB
			101	Accepted	46ms	19628 KiB
			102	Accepted	39ms	19568 KiB
			103	Accepted	94ms	21652 KiB
			104	Accepted	46ms	19636 KiB
			105	Accepted	64ms	21828 KiB
			106	Accepted	41ms	19808 KiB
			107	Accepted	45ms	19944 KiB
			108	Accepted	39ms	19516 KiB
			109	Accepted	86ms	21844 KiB
			110	Accepted	39ms	19432 KiB
			111	Accepted	695ms	21772 KiB
			112	Accepted	63ms	21476 KiB
			113	Accepted	46ms	21008 KiB
			114	Accepted	64ms	21724 KiB
			115	Accepted	45ms	19436 KiB
			116	Accepted	45ms	19568 KiB
			117	Accepted	39ms	19584 KiB
			118	Accepted	39ms	19588 KiB
			119	Accepted	43ms	19684 KiB
			120	Accepted	39ms	19796 KiB
			121	Accepted	37ms	19712 KiB
			122	Accepted	43ms	19688 KiB
			123	Accepted	46ms	21548 KiB
			124	Accepted	46ms	21480 KiB
			125	Accepted	46ms	19584 KiB
			126	Accepted	39ms	19708 KiB
			127	Accepted	52ms	21584 KiB
			128	Accepted	39ms	19692 KiB
			129	Accepted	46ms	19696 KiB
130	Accepted		39ms	19616 KiB
131	Accepted		52ms	21496 KiB
132	Time limit exceeded		1.083s	22136 KiB
133	Accepted		59ms	21404 KiB
134	Time limit exceeded		1.082s	22324 KiB
135	Time limit exceeded		1.083s	22000 KiB
136	Time limit exceeded		1.082s	22388 KiB
137	Time limit exceeded		1.085s	22248 KiB
138	Time limit exceeded		1.087s	22244 KiB
139	Accepted		75ms	23016 KiB
140	Accepted		204ms	23780 KiB
141	Accepted		143ms	23532 KiB
142	Accepted		698ms	24296 KiB
143	Time limit exceeded		1.087s	24260 KiB
144	Accepted		736ms	24552 KiB
145	Time limit exceeded		1.003s	24052 KiB
146	Time limit exceeded		1.08s	25064 KiB
147	Time limit exceeded		1.082s	24808 KiB
148	Time limit exceeded		1.087s	25320 KiB
149	Time limit exceeded		1.088s	24552 KiB