248492026-02-16 02:32:56999Városnézéscpp17Runtime error 0/80508ms262144 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
    int n,m;cin>>n>>m;
    vector<vector<int>> v(n),g(n);
    vector<int> lat(n),fok(n),fr(n);
    for(int i = 0;i<n;i++){
        cin>>lat[i];
    }
    for(int i = 0;i<m;i++){
        int a,b;cin>>a>>b;
        a--;b--;
        v[a].push_back(b);
        g[b].push_back(a);
        fok[a]++;
    }
    vector<int> dp(n,-1);
    queue<int> q;
    for(int i = 0;i<n;i++){
        if(fok[i]==0&&i!=n-1){
            q.push(i);
            dp[i]=-2;
        }
        else if(fok[i]==0&&i==n-1){
            dp[i]=0;
            q.push(i);
        }
    }
    while(!q.empty()){
        int a=q.front();
        q.pop();
        if(dp[a]!=-2)for(int u:v[a]){
            if(dp[a]<dp[u]){
                dp[a]=max(dp[a],dp[u]);
                fr[a]=u;
            }
        }
        if(dp[a]!=-2)dp[a]+=lat[a];
        for(int u : g[a]){
            fok[u]--;
            if(fok[u]==0){
                q.push(u);
            }
        }
    }
    //for(int i : dp)cout<<i<<' ';return 0;
    if(dp[0]<0){
        cout<<-1;
        return 0;
    }
    cout<<dp[0]<<endl;
    int i = 0;
    vector<int> ans;
    while(i!=n-1){
        ans.push_back(i+1);
        i=fr[i];
    }
    ans.push_back(n);
    for(int i : ans)cout<<i<<' ';
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
subtask20/20
2Accepted2ms316 KiB
3Accepted1ms316 KiB
4Runtime error370ms262144 KiB
5Runtime error367ms262144 KiB
6Runtime error483ms262144 KiB
7Runtime error367ms262144 KiB
8Runtime error495ms262144 KiB
9Accepted2ms316 KiB
10Runtime error435ms262144 KiB
11Runtime error372ms262144 KiB
12Runtime error483ms262144 KiB
subtask30/25
13Accepted1ms316 KiB
14Accepted1ms316 KiB
15Accepted1ms316 KiB
16Accepted1ms316 KiB
17Accepted1ms316 KiB
18Accepted1ms316 KiB
19Accepted1ms316 KiB
20Accepted1ms316 KiB
21Accepted1ms508 KiB
22Accepted3ms344 KiB
23Accepted2ms588 KiB
24Accepted4ms580 KiB
25Accepted2ms500 KiB
26Accepted3ms580 KiB
27Accepted4ms564 KiB
28Accepted28ms1704 KiB
29Accepted6ms564 KiB
30Accepted32ms1924 KiB
31Runtime error486ms262144 KiB
32Accepted39ms2436 KiB
33Accepted12ms2100 KiB
subtask40/20
34Accepted1ms316 KiB
35Wrong answer2ms316 KiB
36Accepted1ms316 KiB
37Wrong answer1ms316 KiB
38Wrong answer1ms316 KiB
39Accepted1ms316 KiB
40Runtime error477ms262144 KiB
41Runtime error472ms262144 KiB
42Accepted1ms316 KiB
43Accepted1ms316 KiB
44Wrong answer1ms316 KiB
45Runtime error479ms262144 KiB
46Wrong answer1ms316 KiB
47Wrong answer1ms316 KiB
48Accepted1ms316 KiB
49Runtime error430ms262144 KiB
50Accepted1ms500 KiB
51Accepted1ms316 KiB
52Accepted1ms336 KiB
53Runtime error360ms262144 KiB
54Accepted1ms316 KiB
55Accepted1ms316 KiB
56Accepted2ms508 KiB
57Accepted1ms316 KiB
58Accepted1ms500 KiB
59Accepted1ms316 KiB
60Accepted1ms316 KiB
61Accepted1ms324 KiB
62Runtime error453ms262144 KiB
63Accepted2ms316 KiB
64Accepted1ms316 KiB
65Accepted1ms316 KiB
66Accepted1ms316 KiB
subtask50/15
67Accepted1ms316 KiB
68Accepted2ms316 KiB
69Accepted1ms316 KiB
70Runtime error370ms262144 KiB
71Runtime error367ms262144 KiB
72Runtime error483ms262144 KiB
73Runtime error367ms262144 KiB
74Runtime error495ms262144 KiB
75Accepted2ms316 KiB
76Runtime error435ms262144 KiB
77Runtime error372ms262144 KiB
78Runtime error483ms262144 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted1ms316 KiB
83Accepted1ms316 KiB
84Accepted1ms316 KiB
85Accepted1ms316 KiB
86Accepted1ms316 KiB
87Accepted1ms508 KiB
88Accepted3ms344 KiB
89Accepted2ms588 KiB
90Accepted4ms580 KiB
91Accepted2ms500 KiB
92Accepted3ms580 KiB
93Accepted4ms564 KiB
94Accepted28ms1704 KiB
95Accepted6ms564 KiB
96Accepted32ms1924 KiB
97Runtime error486ms262144 KiB
98Accepted39ms2436 KiB
99Accepted12ms2100 KiB
100Wrong answer2ms316 KiB
101Accepted1ms316 KiB
102Wrong answer1ms316 KiB
103Wrong answer1ms316 KiB
104Accepted1ms316 KiB
105Runtime error477ms262144 KiB
106Runtime error472ms262144 KiB
107Accepted1ms316 KiB
108Accepted1ms316 KiB
109Wrong answer1ms316 KiB
110Runtime error479ms262144 KiB
111Wrong answer1ms316 KiB
112Wrong answer1ms316 KiB
113Accepted1ms316 KiB
114Runtime error430ms262144 KiB
115Accepted1ms500 KiB
116Accepted1ms316 KiB
117Accepted1ms336 KiB
118Runtime error360ms262144 KiB
119Accepted1ms316 KiB
120Accepted1ms316 KiB
121Accepted2ms508 KiB
122Accepted1ms316 KiB
123Accepted1ms500 KiB
124Accepted1ms316 KiB
125Accepted1ms316 KiB
126Accepted1ms324 KiB
127Runtime error453ms262144 KiB
128Accepted2ms316 KiB
129Accepted1ms316 KiB
130Accepted1ms316 KiB
131Accepted1ms316 KiB
132Runtime error477ms262144 KiB
133Accepted2ms568 KiB
134Runtime error363ms262144 KiB
135Runtime error361ms262144 KiB
136Runtime error470ms262144 KiB
137Runtime error474ms262144 KiB
138Runtime error358ms262144 KiB
139Accepted4ms748 KiB
140Runtime error363ms262144 KiB
141Runtime error481ms262144 KiB
142Runtime error377ms262144 KiB
143Accepted10ms1588 KiB
144Runtime error483ms262144 KiB
145Runtime error412ms262144 KiB
146Runtime error508ms262144 KiB
147Accepted18ms2368 KiB
148Accepted17ms1844 KiB
149Accepted12ms1076 KiB