248462026-02-16 02:21:50999Városnézéscpp17Runtime error 0/80505ms262144 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);
    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);
    queue<int> q;
    for(int i = 0;i<n;i++){
        if(fok[i]==0&&i!=n-1){
            q.push(i);
            dp[i]=INT_MIN;
        }
        else if(fok[i]==0&&i==n-1){
            q.push(i);
        }
    }
    while(!q.empty()){
        int a=q.front();
        q.pop();
        if(dp[a]!=INT_MIN)for(int u:v[a])dp[a]=max(dp[a],dp[u]);
        if(dp[a]!=INT_MIN)dp[a]+=lat[a];
        for(int u : g[a]){
            fok[u]--;
            if(fok[u]==0){
                q.push(u);
            }
        }
    }
    int i = 0;
    vector<int> ans;
    while(1){
        ans.push_back(i+1);
        if(i==n-1)break;
        for(int u : v[i]){
            if(dp[u]+lat[i]==dp[i]){
                i=u;
                break;
            }
        }
    }
    cout<<dp[0]<<endl;
    for(int i : ans)cout<<i<<' ';
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms508 KiB
subtask20/20
2Accepted2ms356 KiB
3Accepted2ms316 KiB
4Runtime error485ms262144 KiB
5Runtime error384ms262144 KiB
6Runtime error485ms262144 KiB
7Runtime error379ms262144 KiB
8Runtime error492ms262144 KiB
9Accepted1ms316 KiB
10Runtime error382ms262144 KiB
11Runtime error483ms262144 KiB
12Runtime error372ms262144 KiB
subtask30/25
13Accepted2ms512 KiB
14Accepted2ms316 KiB
15Accepted1ms500 KiB
16Accepted2ms316 KiB
17Accepted1ms316 KiB
18Accepted1ms356 KiB
19Accepted1ms316 KiB
20Runtime error349ms262144 KiB
21Runtime error458ms262144 KiB
22Accepted3ms508 KiB
23Runtime error453ms262144 KiB
24Accepted4ms564 KiB
25Accepted3ms316 KiB
26Runtime error347ms262144 KiB
27Runtime error347ms262144 KiB
28Accepted28ms1620 KiB
29Accepted6ms544 KiB
30Accepted30ms1968 KiB
31Runtime error437ms262144 KiB
32Runtime error488ms262144 KiB
33Runtime error462ms262144 KiB
subtask40/20
34Accepted1ms316 KiB
35Accepted1ms316 KiB
36Accepted1ms316 KiB
37Accepted1ms316 KiB
38Wrong answer1ms316 KiB
39Accepted1ms500 KiB
40Runtime error375ms262144 KiB
41Runtime error505ms262144 KiB
42Runtime error455ms262144 KiB
43Runtime error342ms262144 KiB
44Wrong answer1ms512 KiB
45Runtime error365ms262144 KiB
46Wrong answer1ms316 KiB
47Wrong answer1ms508 KiB
48Runtime error354ms262144 KiB
49Runtime error451ms262144 KiB
50Accepted1ms316 KiB
51Accepted1ms316 KiB
52Accepted1ms316 KiB
53Runtime error483ms262144 KiB
54Accepted1ms316 KiB
55Accepted1ms316 KiB
56Accepted1ms316 KiB
57Accepted1ms316 KiB
58Accepted1ms316 KiB
59Accepted1ms316 KiB
60Accepted1ms508 KiB
61Accepted1ms316 KiB
62Runtime error365ms262144 KiB
63Accepted1ms316 KiB
64Accepted1ms316 KiB
65Accepted1ms316 KiB
66Accepted1ms316 KiB
subtask50/15
67Accepted1ms316 KiB
68Accepted2ms356 KiB
69Accepted2ms316 KiB
70Runtime error485ms262144 KiB
71Runtime error384ms262144 KiB
72Runtime error485ms262144 KiB
73Runtime error379ms262144 KiB
74Runtime error492ms262144 KiB
75Accepted1ms316 KiB
76Runtime error382ms262144 KiB
77Runtime error483ms262144 KiB
78Runtime error372ms262144 KiB
79Accepted2ms512 KiB
80Accepted2ms316 KiB
81Accepted1ms500 KiB
82Accepted2ms316 KiB
83Accepted1ms316 KiB
84Accepted1ms356 KiB
85Accepted1ms316 KiB
86Runtime error349ms262144 KiB
87Runtime error458ms262144 KiB
88Accepted3ms508 KiB
89Runtime error453ms262144 KiB
90Accepted4ms564 KiB
91Accepted3ms316 KiB
92Runtime error347ms262144 KiB
93Runtime error347ms262144 KiB
94Accepted28ms1620 KiB
95Accepted6ms544 KiB
96Accepted30ms1968 KiB
97Runtime error437ms262144 KiB
98Runtime error488ms262144 KiB
99Runtime error462ms262144 KiB
100Accepted1ms316 KiB
101Accepted1ms316 KiB
102Accepted1ms316 KiB
103Wrong answer1ms316 KiB
104Accepted1ms500 KiB
105Runtime error375ms262144 KiB
106Runtime error505ms262144 KiB
107Runtime error455ms262144 KiB
108Runtime error342ms262144 KiB
109Wrong answer1ms512 KiB
110Runtime error365ms262144 KiB
111Wrong answer1ms316 KiB
112Wrong answer1ms508 KiB
113Runtime error354ms262144 KiB
114Runtime error451ms262144 KiB
115Accepted1ms316 KiB
116Accepted1ms316 KiB
117Accepted1ms316 KiB
118Runtime error483ms262144 KiB
119Accepted1ms316 KiB
120Accepted1ms316 KiB
121Accepted1ms316 KiB
122Accepted1ms316 KiB
123Accepted1ms316 KiB
124Accepted1ms316 KiB
125Accepted1ms508 KiB
126Accepted1ms316 KiB
127Runtime error365ms262144 KiB
128Accepted1ms316 KiB
129Accepted1ms316 KiB
130Accepted1ms316 KiB
131Accepted1ms316 KiB
132Runtime error485ms262144 KiB
133Runtime error347ms262144 KiB
134Runtime error483ms262144 KiB
135Runtime error379ms262144 KiB
136Runtime error370ms262144 KiB
137Runtime error430ms262144 KiB
138Runtime error370ms262144 KiB
139Runtime error456ms262144 KiB
140Runtime error372ms262144 KiB
141Runtime error474ms262144 KiB
142Runtime error375ms262144 KiB
143Accepted10ms1332 KiB
144Runtime error460ms262144 KiB
145Runtime error377ms262144 KiB
146Runtime error497ms262144 KiB
147Accepted19ms2180 KiB
148Accepted17ms1844 KiB
149Accepted12ms1076 KiB