217792026-01-13 22:00:28szabelrVárosnézéscpp17Wrong answer 20/80535ms262144 KiB
// Városnézés topologia.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    vector<int> latv(n + 1);
    vector<int> indegree(n + 1,0);
    vector<int> maxlatv(n + 1,-1);
    vector<int>honnan(n + 1);
    honnan[1] = -1;
    for (int i = 1; i <= n; i++)
    {
        int x; cin >> x;
        latv[i] = x;
    }
    maxlatv[1] = latv[1];
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        indegree[y]++;
    }
    queue<int> q;
    q.push(1);
    while (!q.empty())
    {
        int v = q.front();
        q.pop();
        for (auto next : adj[v])
        {
            indegree[next]--;
            if (maxlatv[v] + latv[next] > maxlatv[next])
            {
                maxlatv[next] = maxlatv[v] + latv[next];
                honnan[next] = v;
            }
            if (indegree[next] == 0)
            {
                q.push(next);
            }
        }
    }
    cout << maxlatv[n] << endl;
    int x = honnan[n];
    vector<int>res;
    res.push_back(n);
    while (x != -1)
    {
        res.push_back(x);
        x = honnan[x];
    }
    reverse(res.begin(), res.end());
    for (auto x : res)
        cout << x << " ";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
subtask220/20
2Accepted1ms500 KiB
3Accepted2ms316 KiB
4Accepted1ms500 KiB
5Accepted3ms564 KiB
6Accepted2ms324 KiB
7Accepted4ms740 KiB
8Accepted4ms820 KiB
9Accepted1ms316 KiB
10Accepted7ms1332 KiB
11Accepted1ms500 KiB
12Accepted1ms316 KiB
subtask30/25
13Wrong answer1ms316 KiB
14Accepted1ms332 KiB
15Wrong answer1ms316 KiB
16Wrong answer1ms316 KiB
17Accepted1ms316 KiB
18Runtime error418ms262144 KiB
19Accepted1ms500 KiB
20Runtime error411ms262144 KiB
21Runtime error533ms262144 KiB
22Runtime error416ms262144 KiB
23Runtime error414ms262144 KiB
24Runtime error535ms262144 KiB
25Runtime error411ms262144 KiB
26Runtime error527ms262144 KiB
27Runtime error421ms262144 KiB
28Runtime error412ms262144 KiB
29Runtime error411ms262144 KiB
30Runtime error526ms262144 KiB
31Runtime error456ms262144 KiB
32Runtime error414ms262144 KiB
33Runtime error528ms262144 KiB
subtask40/20
34Accepted1ms316 KiB
35Wrong answer1ms492 KiB
36Accepted1ms508 KiB
37Wrong answer1ms316 KiB
38Runtime error522ms262144 KiB
39Accepted1ms316 KiB
40Runtime error405ms262144 KiB
41Runtime error404ms262144 KiB
42Runtime error405ms262144 KiB
43Runtime error404ms262144 KiB
44Runtime error521ms262144 KiB
45Runtime error400ms262144 KiB
46Runtime error522ms262144 KiB
47Runtime error402ms262144 KiB
48Runtime error407ms262144 KiB
49Runtime error414ms262144 KiB
50Accepted1ms316 KiB
51Accepted1ms316 KiB
52Wrong answer1ms504 KiB
53Accepted1ms316 KiB
54Accepted1ms316 KiB
55Wrong answer1ms316 KiB
56Wrong answer1ms316 KiB
57Wrong answer1ms356 KiB
58Accepted1ms316 KiB
59Wrong answer1ms316 KiB
60Accepted1ms316 KiB
61Accepted1ms316 KiB
62Wrong answer1ms316 KiB
63Wrong answer1ms316 KiB
64Accepted1ms316 KiB
65Accepted1ms316 KiB
66Accepted1ms316 KiB
subtask50/15
67Accepted1ms316 KiB
68Accepted1ms500 KiB
69Accepted2ms316 KiB
70Accepted1ms500 KiB
71Accepted3ms564 KiB
72Accepted2ms324 KiB
73Accepted4ms740 KiB
74Accepted4ms820 KiB
75Accepted1ms316 KiB
76Accepted7ms1332 KiB
77Accepted1ms500 KiB
78Accepted1ms316 KiB
79Wrong answer1ms316 KiB
80Accepted1ms332 KiB
81Wrong answer1ms316 KiB
82Wrong answer1ms316 KiB
83Accepted1ms316 KiB
84Runtime error418ms262144 KiB
85Accepted1ms500 KiB
86Runtime error411ms262144 KiB
87Runtime error533ms262144 KiB
88Runtime error416ms262144 KiB
89Runtime error414ms262144 KiB
90Runtime error535ms262144 KiB
91Runtime error411ms262144 KiB
92Runtime error527ms262144 KiB
93Runtime error421ms262144 KiB
94Runtime error412ms262144 KiB
95Runtime error411ms262144 KiB
96Runtime error526ms262144 KiB
97Runtime error456ms262144 KiB
98Runtime error414ms262144 KiB
99Runtime error528ms262144 KiB
100Wrong answer1ms492 KiB
101Accepted1ms508 KiB
102Wrong answer1ms316 KiB
103Runtime error522ms262144 KiB
104Accepted1ms316 KiB
105Runtime error405ms262144 KiB
106Runtime error404ms262144 KiB
107Runtime error405ms262144 KiB
108Runtime error404ms262144 KiB
109Runtime error521ms262144 KiB
110Runtime error400ms262144 KiB
111Runtime error522ms262144 KiB
112Runtime error402ms262144 KiB
113Runtime error407ms262144 KiB
114Runtime error414ms262144 KiB
115Accepted1ms316 KiB
116Accepted1ms316 KiB
117Wrong answer1ms504 KiB
118Accepted1ms316 KiB
119Accepted1ms316 KiB
120Wrong answer1ms316 KiB
121Wrong answer1ms316 KiB
122Wrong answer1ms356 KiB
123Accepted1ms316 KiB
124Wrong answer1ms316 KiB
125Accepted1ms316 KiB
126Accepted1ms316 KiB
127Wrong answer1ms316 KiB
128Wrong answer1ms316 KiB
129Accepted1ms316 KiB
130Accepted1ms316 KiB
131Accepted1ms316 KiB
132Runtime error523ms262144 KiB
133Runtime error412ms262144 KiB
134Runtime error519ms262144 KiB
135Runtime error456ms262144 KiB
136Runtime error518ms262144 KiB
137Runtime error430ms262144 KiB
138Runtime error398ms262144 KiB
139Runtime error515ms262144 KiB
140Accepted3ms564 KiB
141Wrong answer1ms316 KiB
142Wrong answer4ms740 KiB
143Wrong answer4ms820 KiB
144Accepted6ms1076 KiB
145Wrong answer4ms928 KiB
146Accepted9ms1592 KiB
147Wrong answer7ms1468 KiB
148Wrong answer4ms820 KiB
149Wrong answer3ms564 KiB