248472026-02-16 02:22:57999Városnézéscpp17Hibás válasz 0/8037ms2980 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);
            }
        }
    }
    cout<<dp[0]<<endl; return 0;
    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;
            }
        }
    }
    for(int i : ans)cout<<i<<' ';
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Hibás válasz1ms316 KiB
subtask20/20
2Hibás válasz2ms316 KiB
3Hibás válasz2ms552 KiB
4Hibás válasz2ms316 KiB
5Hibás válasz6ms820 KiB
6Hibás válasz3ms564 KiB
7Hibás válasz8ms1352 KiB
8Hibás válasz8ms1408 KiB
9Hibás válasz1ms316 KiB
10Hibás válasz16ms2092 KiB
11Hibás válasz1ms316 KiB
12Hibás válasz1ms500 KiB
subtask30/25
13Hibás válasz1ms316 KiB
14Hibás válasz1ms508 KiB
15Hibás válasz1ms316 KiB
16Hibás válasz1ms500 KiB
17Hibás válasz1ms316 KiB
18Hibás válasz1ms604 KiB
19Hibás válasz1ms316 KiB
20Hibás válasz1ms392 KiB
21Hibás válasz1ms388 KiB
22Hibás válasz4ms564 KiB
23Hibás válasz2ms520 KiB
24Hibás válasz4ms316 KiB
25Hibás válasz3ms636 KiB
26Hibás válasz3ms564 KiB
27Hibás válasz4ms564 KiB
28Hibás válasz28ms1632 KiB
29Hibás válasz6ms564 KiB
30Hibás válasz30ms1848 KiB
31Hibás válasz17ms1660 KiB
32Hibás válasz37ms2868 KiB
33Hibás válasz10ms2108 KiB
subtask40/20
34Hibás válasz1ms316 KiB
35Hibás válasz1ms508 KiB
36Hibás válasz1ms316 KiB
37Hibás válasz1ms316 KiB
38Hibás válasz1ms544 KiB
39Hibás válasz1ms316 KiB
40Hibás válasz1ms508 KiB
41Hibás válasz1ms564 KiB
42Hibás válasz1ms316 KiB
43Hibás válasz1ms316 KiB
44Hibás válasz1ms316 KiB
45Hibás válasz1ms316 KiB
46Hibás válasz1ms316 KiB
47Hibás válasz1ms316 KiB
48Hibás válasz1ms500 KiB
49Hibás válasz1ms316 KiB
50Hibás válasz1ms332 KiB
51Hibás válasz1ms316 KiB
52Hibás válasz1ms316 KiB
53Hibás válasz1ms316 KiB
54Hibás válasz1ms316 KiB
55Hibás válasz1ms500 KiB
56Hibás válasz1ms380 KiB
57Hibás válasz1ms316 KiB
58Hibás válasz1ms316 KiB
59Hibás válasz1ms316 KiB
60Hibás válasz1ms316 KiB
61Hibás válasz1ms316 KiB
62Hibás válasz1ms316 KiB
63Hibás válasz2ms316 KiB
64Hibás válasz1ms500 KiB
65Hibás válasz1ms316 KiB
66Hibás válasz1ms316 KiB
subtask50/15
67Hibás válasz1ms316 KiB
68Hibás válasz2ms316 KiB
69Hibás válasz2ms552 KiB
70Hibás válasz2ms316 KiB
71Hibás válasz6ms820 KiB
72Hibás válasz3ms564 KiB
73Hibás válasz8ms1352 KiB
74Hibás válasz8ms1408 KiB
75Hibás válasz1ms316 KiB
76Hibás válasz16ms2092 KiB
77Hibás válasz1ms316 KiB
78Hibás válasz1ms500 KiB
79Hibás válasz1ms316 KiB
80Hibás válasz1ms508 KiB
81Hibás válasz1ms316 KiB
82Hibás válasz1ms500 KiB
83Hibás válasz1ms316 KiB
84Hibás válasz1ms604 KiB
85Hibás válasz1ms316 KiB
86Hibás válasz1ms392 KiB
87Hibás válasz1ms388 KiB
88Hibás válasz4ms564 KiB
89Hibás válasz2ms520 KiB
90Hibás válasz4ms316 KiB
91Hibás válasz3ms636 KiB
92Hibás válasz3ms564 KiB
93Hibás válasz4ms564 KiB
94Hibás válasz28ms1632 KiB
95Hibás válasz6ms564 KiB
96Hibás válasz30ms1848 KiB
97Hibás válasz17ms1660 KiB
98Hibás válasz37ms2868 KiB
99Hibás válasz10ms2108 KiB
100Hibás válasz1ms508 KiB
101Hibás válasz1ms316 KiB
102Hibás válasz1ms316 KiB
103Hibás válasz1ms544 KiB
104Hibás válasz1ms316 KiB
105Hibás válasz1ms508 KiB
106Hibás válasz1ms564 KiB
107Hibás válasz1ms316 KiB
108Hibás válasz1ms316 KiB
109Hibás válasz1ms316 KiB
110Hibás válasz1ms316 KiB
111Hibás válasz1ms316 KiB
112Hibás válasz1ms316 KiB
113Hibás válasz1ms500 KiB
114Hibás válasz1ms316 KiB
115Hibás válasz1ms332 KiB
116Hibás válasz1ms316 KiB
117Hibás válasz1ms316 KiB
118Hibás válasz1ms316 KiB
119Hibás válasz1ms316 KiB
120Hibás válasz1ms500 KiB
121Hibás válasz1ms380 KiB
122Hibás válasz1ms316 KiB
123Hibás válasz1ms316 KiB
124Hibás válasz1ms316 KiB
125Hibás válasz1ms316 KiB
126Hibás válasz1ms316 KiB
127Hibás válasz1ms316 KiB
128Hibás válasz2ms316 KiB
129Hibás válasz1ms500 KiB
130Hibás válasz1ms316 KiB
131Hibás válasz1ms316 KiB
132Hibás válasz4ms564 KiB
133Hibás válasz2ms564 KiB
134Hibás válasz4ms564 KiB
135Hibás válasz2ms316 KiB
136Hibás válasz3ms548 KiB
137Hibás válasz2ms316 KiB
138Hibás válasz3ms316 KiB
139Hibás válasz3ms564 KiB
140Hibás válasz7ms820 KiB
141Hibás válasz4ms564 KiB
142Hibás válasz10ms1332 KiB
143Hibás válasz10ms1536 KiB
144Hibás válasz14ms1964 KiB
145Hibás válasz8ms1336 KiB
146Hibás válasz25ms2980 KiB
147Hibás válasz18ms2356 KiB
148Hibás válasz17ms1776 KiB
149Hibás válasz12ms928 KiB