Submission #19,113

19113

2025-11-24 19:26:59

python3

Time limit exceeded 65/80

1.1s

10628 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	16ms	3232 KiB
	subtask2	20/20
			2	Accepted	16ms	3312 KiB
			3	Accepted	17ms	3108 KiB
			4	Accepted	17ms	3120 KiB
			5	Accepted	37ms	5008 KiB
			6	Accepted	25ms	3912 KiB
			7	Accepted	54ms	6316 KiB
			8	Accepted	54ms	6392 KiB
			9	Accepted	16ms	3144 KiB
			10	Accepted	79ms	8412 KiB
			11	Accepted	16ms	3124 KiB
			12	Accepted	16ms	3204 KiB
	subtask3	25/25
			13	Accepted	17ms	3212 KiB
			14	Accepted	17ms	3124 KiB
			15	Accepted	17ms	3120 KiB
			16	Accepted	17ms	3124 KiB
			17	Accepted	17ms	3080 KiB
			18	Accepted	17ms	3312 KiB
			19	Accepted	16ms	3324 KiB
			20	Accepted	17ms	3320 KiB
			21	Accepted	17ms	3032 KiB
			22	Accepted	92ms	3408 KiB
			23	Accepted	19ms	3620 KiB
			24	Accepted	52ms	3548 KiB
			25	Accepted	25ms	3384 KiB
			26	Accepted	21ms	3380 KiB
			27	Accepted	28ms	3608 KiB
			28	Accepted	303ms	6424 KiB
			29	Accepted	32ms	4080 KiB
			30	Accepted	141ms	7332 KiB
			31	Accepted	70ms	6076 KiB
			32	Accepted	128ms	7476 KiB
			33	Accepted	50ms	6900 KiB
	subtask4	20/20
			34	Accepted	17ms	3128 KiB
			35	Accepted	17ms	3320 KiB
			36	Accepted	16ms	3320 KiB
			37	Accepted	17ms	3120 KiB
			38	Accepted	17ms	3312 KiB
			39	Accepted	17ms	3164 KiB
			40	Accepted	17ms	3312 KiB
			41	Accepted	17ms	3124 KiB
			42	Accepted	17ms	3284 KiB
			43	Accepted	16ms	3124 KiB
			44	Accepted	16ms	3124 KiB
			45	Accepted	17ms	3124 KiB
			46	Accepted	17ms	3220 KiB
			47	Accepted	17ms	3124 KiB
			48	Accepted	17ms	3260 KiB
			49	Accepted	17ms	3288 KiB
			50	Accepted	17ms	3436 KiB
			51	Accepted	17ms	3568 KiB
			52	Accepted	17ms	3116 KiB
			53	Accepted	16ms	3076 KiB
			54	Accepted	17ms	3052 KiB
			55	Accepted	16ms	3060 KiB
			56	Accepted	16ms	3148 KiB
			57	Accepted	17ms	3124 KiB
			58	Accepted	17ms	3124 KiB
			59	Accepted	17ms	3148 KiB
			60	Accepted	17ms	3120 KiB
			61	Accepted	17ms	3124 KiB
			62	Accepted	17ms	3144 KiB
			63	Accepted	16ms	3120 KiB
			64	Accepted	16ms	3120 KiB
			65	Accepted	16ms	3120 KiB
			66	Accepted	16ms	3320 KiB
	subtask5	0/15
			67	Accepted	17ms	3128 KiB
			68	Accepted	16ms	3312 KiB
			69	Accepted	17ms	3108 KiB
			70	Accepted	17ms	3120 KiB
			71	Accepted	37ms	5008 KiB
			72	Accepted	25ms	3912 KiB
			73	Accepted	54ms	6316 KiB
			74	Accepted	54ms	6392 KiB
			75	Accepted	16ms	3144 KiB
			76	Accepted	79ms	8412 KiB
			77	Accepted	16ms	3124 KiB
			78	Accepted	16ms	3204 KiB
			79	Accepted	17ms	3212 KiB
			80	Accepted	17ms	3124 KiB
			81	Accepted	17ms	3120 KiB
			82	Accepted	17ms	3124 KiB
			83	Accepted	17ms	3080 KiB
			84	Accepted	17ms	3312 KiB
			85	Accepted	16ms	3324 KiB
			86	Accepted	17ms	3320 KiB
			87	Accepted	17ms	3032 KiB
			88	Accepted	92ms	3408 KiB
			89	Accepted	19ms	3620 KiB
			90	Accepted	52ms	3548 KiB
			91	Accepted	25ms	3384 KiB
			92	Accepted	21ms	3380 KiB
			93	Accepted	28ms	3608 KiB
			94	Accepted	303ms	6424 KiB
			95	Accepted	32ms	4080 KiB
			96	Accepted	141ms	7332 KiB
			97	Accepted	70ms	6076 KiB
			98	Accepted	128ms	7476 KiB
			99	Accepted	50ms	6900 KiB
			100	Accepted	17ms	3320 KiB
			101	Accepted	16ms	3320 KiB
			102	Accepted	17ms	3120 KiB
			103	Accepted	17ms	3312 KiB
			104	Accepted	17ms	3164 KiB
			105	Accepted	17ms	3312 KiB
			106	Accepted	17ms	3124 KiB
			107	Accepted	17ms	3284 KiB
			108	Accepted	16ms	3124 KiB
			109	Accepted	16ms	3124 KiB
			110	Accepted	17ms	3124 KiB
			111	Accepted	17ms	3220 KiB
			112	Accepted	17ms	3124 KiB
			113	Accepted	17ms	3260 KiB
			114	Accepted	17ms	3288 KiB
			115	Accepted	17ms	3436 KiB
			116	Accepted	17ms	3568 KiB
			117	Accepted	17ms	3116 KiB
			118	Accepted	16ms	3076 KiB
			119	Accepted	17ms	3052 KiB
			120	Accepted	16ms	3060 KiB
			121	Accepted	16ms	3148 KiB
			122	Accepted	17ms	3124 KiB
			123	Accepted	17ms	3124 KiB
			124	Accepted	17ms	3148 KiB
			125	Accepted	17ms	3120 KiB
			126	Accepted	17ms	3124 KiB
			127	Accepted	17ms	3144 KiB
			128	Accepted	16ms	3120 KiB
			129	Accepted	16ms	3120 KiB
130	Accepted		16ms	3120 KiB
131	Accepted		16ms	3320 KiB
132	Accepted		67ms	3240 KiB
133	Accepted		18ms	3636 KiB
134	Accepted		46ms	3424 KiB
135	Accepted		25ms	3296 KiB
136	Accepted		32ms	3384 KiB
137	Accepted		24ms	3352 KiB
138	Accepted		57ms	3128 KiB
139	Accepted		21ms	3520 KiB
140	Accepted		37ms	4824 KiB
141	Accepted		28ms	3956 KiB
142	Accepted		61ms	6308 KiB
143	Accepted		83ms	6560 KiB
144	Accepted		67ms	7416 KiB
145	Accepted		59ms	6304 KiB
146	Accepted		119ms	10628 KiB
147	Accepted		717ms	9124 KiB
148	Time limit exceeded		1.1s	7112 KiB
149	Time limit exceeded		1.098s	5152 KiB