241112026-02-04 13:01:06domdiridomdidomVárosnézéscpp17Runtime error 0/80537ms262144 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) {
    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), ut;
    vector<vector<int>> graf(n);
    for(int i = 0; i < n; i++)
        std::cin >> ertek[i];
    for(int i = 0; i < n; 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);
    for(int i = n - 1; i != -1; i = parent[i])
        ut.push_back(i);
    std::cout << dp[n - 1] << '\n';
    for(int i = 0; i < parent.size(); i++)
        std::cout << parent[i] + 1 << ' ';
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Runtime error411ms262144 KiB
subtask20/20
2Runtime error419ms262144 KiB
3Runtime error1ms500 KiB
4Runtime error1ms316 KiB
5Runtime error537ms262144 KiB
6Runtime error423ms262144 KiB
7Runtime error537ms262144 KiB
8Runtime error435ms262144 KiB
9Runtime error528ms262144 KiB
10Runtime error432ms262144 KiB
11Runtime error527ms262144 KiB
12Runtime error416ms262144 KiB
subtask30/25
13Runtime error528ms262144 KiB
14Runtime error1ms316 KiB
15Runtime error448ms262144 KiB
16Runtime error407ms262144 KiB
17Runtime error524ms262144 KiB
18Runtime error522ms262144 KiB
19Runtime error421ms262144 KiB
20Runtime error416ms262144 KiB
21Runtime error2ms316 KiB
22Runtime error411ms262144 KiB
23Runtime error409ms262144 KiB
24Runtime error517ms262144 KiB
25Runtime error514ms262144 KiB
26Runtime error532ms262144 KiB
27Runtime error412ms262144 KiB
28Runtime error533ms262144 KiB
29Runtime error421ms262144 KiB
30Runtime error425ms262144 KiB
31Runtime error533ms262144 KiB
32Runtime error433ms262144 KiB
33Runtime error12ms1780 KiB
subtask40/20
34Runtime error531ms262144 KiB
35Runtime error435ms262144 KiB
36Runtime error2ms500 KiB
37Runtime error528ms262144 KiB
38Runtime error425ms262144 KiB
39Runtime error2ms508 KiB
40Runtime error523ms262144 KiB
41Runtime error523ms262144 KiB
42Runtime error1ms400 KiB
43Runtime error414ms262144 KiB
44Runtime error409ms262144 KiB
45Runtime error2ms316 KiB
46Runtime error529ms262144 KiB
47Runtime error522ms262144 KiB
48Runtime error426ms262144 KiB
49Runtime error426ms262144 KiB
50Runtime error469ms262144 KiB
51Runtime error532ms262144 KiB
52Runtime error423ms262144 KiB
53Runtime error531ms262144 KiB
54Runtime error423ms262144 KiB
55Runtime error532ms262144 KiB
56Runtime error435ms262144 KiB
57Runtime error532ms262144 KiB
58Runtime error416ms262144 KiB
59Runtime error418ms262144 KiB
60Runtime error519ms262144 KiB
61Runtime error527ms262144 KiB
62Runtime error526ms262144 KiB
63Runtime error444ms262144 KiB
64Runtime error418ms262144 KiB
65Runtime error526ms262144 KiB
66Runtime error537ms262144 KiB
subtask50/15
67Runtime error531ms262144 KiB
68Runtime error419ms262144 KiB
69Runtime error1ms500 KiB
70Runtime error1ms316 KiB
71Runtime error537ms262144 KiB
72Runtime error423ms262144 KiB
73Runtime error537ms262144 KiB
74Runtime error435ms262144 KiB
75Runtime error528ms262144 KiB
76Runtime error432ms262144 KiB
77Runtime error527ms262144 KiB
78Runtime error416ms262144 KiB
79Runtime error528ms262144 KiB
80Runtime error1ms316 KiB
81Runtime error448ms262144 KiB
82Runtime error407ms262144 KiB
83Runtime error524ms262144 KiB
84Runtime error522ms262144 KiB
85Runtime error421ms262144 KiB
86Runtime error416ms262144 KiB
87Runtime error2ms316 KiB
88Runtime error411ms262144 KiB
89Runtime error409ms262144 KiB
90Runtime error517ms262144 KiB
91Runtime error514ms262144 KiB
92Runtime error532ms262144 KiB
93Runtime error412ms262144 KiB
94Runtime error533ms262144 KiB
95Runtime error421ms262144 KiB
96Runtime error425ms262144 KiB
97Runtime error533ms262144 KiB
98Runtime error433ms262144 KiB
99Runtime error12ms1780 KiB
100Runtime error435ms262144 KiB
101Runtime error2ms500 KiB
102Runtime error528ms262144 KiB
103Runtime error425ms262144 KiB
104Runtime error2ms508 KiB
105Runtime error523ms262144 KiB
106Runtime error523ms262144 KiB
107Runtime error1ms400 KiB
108Runtime error414ms262144 KiB
109Runtime error409ms262144 KiB
110Runtime error2ms316 KiB
111Runtime error529ms262144 KiB
112Runtime error522ms262144 KiB
113Runtime error426ms262144 KiB
114Runtime error426ms262144 KiB
115Runtime error469ms262144 KiB
116Runtime error532ms262144 KiB
117Runtime error423ms262144 KiB
118Runtime error531ms262144 KiB
119Runtime error423ms262144 KiB
120Runtime error532ms262144 KiB
121Runtime error435ms262144 KiB
122Runtime error532ms262144 KiB
123Runtime error416ms262144 KiB
124Runtime error418ms262144 KiB
125Runtime error519ms262144 KiB
126Runtime error527ms262144 KiB
127Runtime error526ms262144 KiB
128Runtime error444ms262144 KiB
129Runtime error418ms262144 KiB
130Runtime error526ms262144 KiB
131Runtime error537ms262144 KiB
132Runtime error414ms262144 KiB
133Runtime error418ms262144 KiB
134Runtime error527ms262144 KiB
135Runtime error518ms262144 KiB
136Runtime error412ms262144 KiB
137Runtime error412ms262144 KiB
138Runtime error425ms262144 KiB
139Runtime error531ms262144 KiB
140Runtime error532ms262144 KiB
141Runtime error536ms262144 KiB
142Runtime error423ms262144 KiB
143Runtime error421ms262144 KiB
144Runtime error423ms262144 KiB
145Runtime error524ms262144 KiB
146Runtime error435ms262144 KiB
147Runtime error532ms262144 KiB
148Runtime error421ms262144 KiB
149Runtime error411ms262144 KiB