248512026-02-16 02:40:08999Városnézéscpp17Runtime error 0/80490ms262144 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),vis(n);
    queue<int> q;
    for(int i = 0;i<n;i++){
        if(fok[i]==0&&i!=n-1){
            vis[i]=1;
            q.push(i);
            dp[i]=-2;
        }
        else if(fok[i]==0&&i==n-1){
            vis[i]=1;
            dp[i]=lat[i];
            q.push(i);
        }
    }
    while(!q.empty()){
        int a=q.front();
        q.pop();
        if(dp[a]!=-2&&a!=n-1){
            for(int u:v[a]){
                if(dp[a]<dp[u]){
                    dp[a]=max(dp[a],dp[u]);
                    fr[a]=u;
                }
            }
            dp[a]+=lat[a];
        }
        for(int u : g[a]){
            fok[u]--;
            if(fok[u]==0&&vis[u]==0){
                vis[u]=1;
                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
2Accepted1ms316 KiB
3Accepted1ms316 KiB
4Runtime error365ms262144 KiB
5Runtime error481ms262144 KiB
6Runtime error361ms262144 KiB
7Runtime error479ms262144 KiB
8Runtime error479ms262144 KiB
9Accepted1ms316 KiB
10Runtime error488ms262144 KiB
11Runtime error361ms262144 KiB
12Runtime error354ms262144 KiB
subtask30/25
13Accepted2ms512 KiB
14Accepted2ms316 KiB
15Accepted2ms316 KiB
16Accepted2ms316 KiB
17Accepted1ms316 KiB
18Accepted1ms316 KiB
19Accepted1ms316 KiB
20Accepted1ms316 KiB
21Accepted1ms316 KiB
22Accepted4ms564 KiB
23Accepted2ms564 KiB
24Accepted4ms564 KiB
25Accepted3ms448 KiB
26Accepted3ms564 KiB
27Accepted4ms568 KiB
28Accepted28ms1780 KiB
29Accepted6ms568 KiB
30Accepted32ms1996 KiB
31Runtime error361ms262144 KiB
32Accepted39ms2364 KiB
33Accepted12ms2356 KiB
subtask40/20
34Accepted1ms500 KiB
35Runtime error358ms262144 KiB
36Accepted1ms316 KiB
37Runtime error470ms262144 KiB
38Runtime error360ms262144 KiB
39Accepted1ms316 KiB
40Runtime error467ms262144 KiB
41Runtime error356ms262144 KiB
42Accepted1ms316 KiB
43Accepted1ms316 KiB
44Runtime error363ms262144 KiB
45Runtime error474ms262144 KiB
46Runtime error470ms262144 KiB
47Runtime error479ms262144 KiB
48Accepted1ms316 KiB
49Runtime error361ms262144 KiB
50Accepted1ms316 KiB
51Accepted1ms316 KiB
52Accepted1ms316 KiB
53Runtime error460ms262144 KiB
54Accepted1ms316 KiB
55Accepted1ms316 KiB
56Accepted1ms316 KiB
57Accepted1ms552 KiB
58Accepted1ms500 KiB
59Accepted1ms316 KiB
60Accepted1ms316 KiB
61Accepted1ms316 KiB
62Runtime error358ms262144 KiB
63Accepted1ms500 KiB
64Accepted1ms316 KiB
65Accepted1ms316 KiB
66Accepted1ms316 KiB
subtask50/15
67Accepted1ms500 KiB
68Accepted1ms316 KiB
69Accepted1ms316 KiB
70Runtime error365ms262144 KiB
71Runtime error481ms262144 KiB
72Runtime error361ms262144 KiB
73Runtime error479ms262144 KiB
74Runtime error479ms262144 KiB
75Accepted1ms316 KiB
76Runtime error488ms262144 KiB
77Runtime error361ms262144 KiB
78Runtime error354ms262144 KiB
79Accepted2ms512 KiB
80Accepted2ms316 KiB
81Accepted2ms316 KiB
82Accepted2ms316 KiB
83Accepted1ms316 KiB
84Accepted1ms316 KiB
85Accepted1ms316 KiB
86Accepted1ms316 KiB
87Accepted1ms316 KiB
88Accepted4ms564 KiB
89Accepted2ms564 KiB
90Accepted4ms564 KiB
91Accepted3ms448 KiB
92Accepted3ms564 KiB
93Accepted4ms568 KiB
94Accepted28ms1780 KiB
95Accepted6ms568 KiB
96Accepted32ms1996 KiB
97Runtime error361ms262144 KiB
98Accepted39ms2364 KiB
99Accepted12ms2356 KiB
100Runtime error358ms262144 KiB
101Accepted1ms316 KiB
102Runtime error470ms262144 KiB
103Runtime error360ms262144 KiB
104Accepted1ms316 KiB
105Runtime error467ms262144 KiB
106Runtime error356ms262144 KiB
107Accepted1ms316 KiB
108Accepted1ms316 KiB
109Runtime error363ms262144 KiB
110Runtime error474ms262144 KiB
111Runtime error470ms262144 KiB
112Runtime error479ms262144 KiB
113Accepted1ms316 KiB
114Runtime error361ms262144 KiB
115Accepted1ms316 KiB
116Accepted1ms316 KiB
117Accepted1ms316 KiB
118Runtime error460ms262144 KiB
119Accepted1ms316 KiB
120Accepted1ms316 KiB
121Accepted1ms316 KiB
122Accepted1ms552 KiB
123Accepted1ms500 KiB
124Accepted1ms316 KiB
125Accepted1ms316 KiB
126Accepted1ms316 KiB
127Runtime error358ms262144 KiB
128Accepted1ms500 KiB
129Accepted1ms316 KiB
130Accepted1ms316 KiB
131Accepted1ms316 KiB
132Runtime error358ms262144 KiB
133Accepted2ms764 KiB
134Runtime error467ms262144 KiB
135Runtime error358ms262144 KiB
136Runtime error460ms262144 KiB
137Runtime error400ms262144 KiB
138Runtime error363ms262144 KiB
139Accepted3ms564 KiB
140Runtime error365ms262144 KiB
141Runtime error458ms262144 KiB
142Runtime error370ms262144 KiB
143Accepted12ms1588 KiB
144Runtime error481ms262144 KiB
145Runtime error405ms262144 KiB
146Runtime error490ms262144 KiB
147Accepted19ms2548 KiB
148Accepted17ms1856 KiB
149Accepted12ms1076 KiB