Submission #24,203

2026-02-06 12:20:31

cpp17

Accepted 80/80

115ms

1688 KiB

#include <iostream>
#include <vector>
#include <climits>

using std::vector;

void rek(vector<int> & ertek, vector<int> & dp, vector<vector<int>> & graf, int u, vector<int> & parent) {
    if(dp[u] == INT_MIN)
        return;
    for(const auto & v : graf[u]) {
        if(dp[u] + ertek[v] > dp[v]) {
            dp[v] = dp[u] + ertek[v];
            parent[v] = u;
            rek(ertek, dp, graf, v, parent);
        }
    }
}

int main() {
    int n, m;
    std::cin >> n >> m;
    vector<int> ertek(n), dp(n, INT_MIN), parent(n, -1), ut;
    vector<vector<int>> graf(n);
    for(int i = 0; i < n; i++)
        std::cin >> ertek[i];
    for(int i = 0; i < m; i++) {
        int u, v;
        std::cin >> u >> v; u--; v--;
        graf[u].push_back(v);
    }
    dp[0] = ertek[0];
    rek(ertek, dp, graf, 0, parent);

    if(dp[n - 1] == INT_MIN)
        std::cout << "-1";
    else {
        std::cout << dp[n - 1] << '\n';
        for(int i = n - 1; i != 0; i = parent[i])
            ut.push_back(i);
        ut.push_back(0);
        for(int i = ut.size() - 1; i >= 0; i--)
            std::cout << ut[i] + 1 << ' ';
    }
}

Subtask		Sum	Test	Verdict	Time	Memory
	subtask1	0/0
	subtask1	0/0	1	Accepted	1ms	316 KiB
	subtask2	20/20
			2	Accepted	2ms	316 KiB
			3	Accepted	2ms	316 KiB
			4	Accepted	2ms	508 KiB
			5	Accepted	6ms	564 KiB
			6	Accepted	3ms	316 KiB
			7	Accepted	8ms	820 KiB
			8	Accepted	8ms	828 KiB
			9	Accepted	1ms	552 KiB
			10	Accepted	16ms	1688 KiB
			11	Accepted	1ms	316 KiB
			12	Accepted	1ms	316 KiB
	subtask3	25/25
			13	Accepted	1ms	316 KiB
			14	Accepted	1ms	316 KiB
			15	Accepted	1ms	316 KiB
			16	Accepted	1ms	316 KiB
			17	Accepted	1ms	536 KiB
			18	Accepted	1ms	316 KiB
			19	Accepted	1ms	340 KiB
			20	Accepted	1ms	508 KiB
			21	Accepted	1ms	316 KiB
			22	Accepted	4ms	316 KiB
			23	Accepted	2ms	316 KiB
			24	Accepted	4ms	316 KiB
			25	Accepted	2ms	316 KiB
			26	Accepted	3ms	500 KiB
			27	Accepted	4ms	316 KiB
			28	Accepted	28ms	644 KiB
			29	Accepted	4ms	316 KiB
			30	Accepted	28ms	916 KiB
			31	Accepted	16ms	792 KiB
			32	Accepted	34ms	1044 KiB
			33	Accepted	9ms	1268 KiB
	subtask4	20/20
			34	Accepted	1ms	508 KiB
			35	Accepted	1ms	316 KiB
			36	Accepted	1ms	508 KiB
			37	Accepted	1ms	316 KiB
			38	Accepted	1ms	316 KiB
			39	Accepted	1ms	316 KiB
			40	Accepted	1ms	384 KiB
			41	Accepted	1ms	316 KiB
			42	Accepted	1ms	316 KiB
			43	Accepted	1ms	316 KiB
			44	Accepted	1ms	316 KiB
			45	Accepted	1ms	316 KiB
			46	Accepted	1ms	316 KiB
			47	Accepted	1ms	316 KiB
			48	Accepted	2ms	316 KiB
			49	Accepted	2ms	316 KiB
			50	Accepted	1ms	316 KiB
			51	Accepted	1ms	500 KiB
			52	Accepted	1ms	508 KiB
			53	Accepted	1ms	316 KiB
			54	Accepted	1ms	316 KiB
			55	Accepted	1ms	316 KiB
			56	Accepted	1ms	508 KiB
			57	Accepted	1ms	500 KiB
			58	Accepted	1ms	332 KiB
			59	Accepted	1ms	548 KiB
			60	Accepted	1ms	348 KiB
			61	Accepted	1ms	316 KiB
			62	Accepted	1ms	508 KiB
			63	Accepted	1ms	316 KiB
			64	Accepted	1ms	548 KiB
			65	Accepted	1ms	316 KiB
			66	Accepted	1ms	316 KiB
	subtask5	15/15
			67	Accepted	1ms	508 KiB
			68	Accepted	2ms	316 KiB
			69	Accepted	2ms	316 KiB
			70	Accepted	2ms	508 KiB
			71	Accepted	6ms	564 KiB
			72	Accepted	3ms	316 KiB
			73	Accepted	8ms	820 KiB
			74	Accepted	8ms	828 KiB
			75	Accepted	1ms	552 KiB
			76	Accepted	16ms	1688 KiB
			77	Accepted	1ms	316 KiB
			78	Accepted	1ms	316 KiB
			79	Accepted	1ms	316 KiB
			80	Accepted	1ms	316 KiB
			81	Accepted	1ms	316 KiB
			82	Accepted	1ms	316 KiB
			83	Accepted	1ms	536 KiB
			84	Accepted	1ms	316 KiB
			85	Accepted	1ms	340 KiB
			86	Accepted	1ms	508 KiB
			87	Accepted	1ms	316 KiB
			88	Accepted	4ms	316 KiB
			89	Accepted	2ms	316 KiB
			90	Accepted	4ms	316 KiB
			91	Accepted	2ms	316 KiB
			92	Accepted	3ms	500 KiB
			93	Accepted	4ms	316 KiB
			94	Accepted	28ms	644 KiB
			95	Accepted	4ms	316 KiB
			96	Accepted	28ms	916 KiB
			97	Accepted	16ms	792 KiB
			98	Accepted	34ms	1044 KiB
			99	Accepted	9ms	1268 KiB
			100	Accepted	1ms	316 KiB
			101	Accepted	1ms	508 KiB
			102	Accepted	1ms	316 KiB
			103	Accepted	1ms	316 KiB
			104	Accepted	1ms	316 KiB
			105	Accepted	1ms	384 KiB
			106	Accepted	1ms	316 KiB
			107	Accepted	1ms	316 KiB
			108	Accepted	1ms	316 KiB
			109	Accepted	1ms	316 KiB
			110	Accepted	1ms	316 KiB
			111	Accepted	1ms	316 KiB
			112	Accepted	1ms	316 KiB
			113	Accepted	2ms	316 KiB
			114	Accepted	2ms	316 KiB
			115	Accepted	1ms	316 KiB
			116	Accepted	1ms	500 KiB
			117	Accepted	1ms	508 KiB
			118	Accepted	1ms	316 KiB
			119	Accepted	1ms	316 KiB
			120	Accepted	1ms	316 KiB
			121	Accepted	1ms	508 KiB
			122	Accepted	1ms	500 KiB
			123	Accepted	1ms	332 KiB
			124	Accepted	1ms	548 KiB
			125	Accepted	1ms	348 KiB
			126	Accepted	1ms	316 KiB
			127	Accepted	1ms	508 KiB
			128	Accepted	1ms	316 KiB
			129	Accepted	1ms	548 KiB
130	Accepted		1ms	316 KiB
131	Accepted		1ms	316 KiB
132	Accepted		4ms	316 KiB
133	Accepted		2ms	316 KiB
134	Accepted		4ms	432 KiB
135	Accepted		2ms	424 KiB
136	Accepted		3ms	316 KiB
137	Accepted		2ms	500 KiB
138	Accepted		3ms	540 KiB
139	Accepted		3ms	508 KiB
140	Accepted		4ms	608 KiB
141	Accepted		3ms	316 KiB
142	Accepted		9ms	860 KiB
143	Accepted		9ms	820 KiB
144	Accepted		12ms	900 KiB
145	Accepted		8ms	940 KiB
146	Accepted		21ms	1604 KiB
147	Accepted		18ms	1332 KiB
148	Accepted		115ms	1184 KiB
149	Accepted		14ms	892 KiB