217812026-01-13 22:03:15szabelrVárosnézéscpp17Wrong answer 20/80529ms262144 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;
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }
    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;
    if(maxlatv[n]!=-1)
    {
        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
2Accepted1ms316 KiB
3Accepted1ms316 KiB
4Accepted1ms500 KiB
5Accepted3ms636 KiB
6Accepted2ms316 KiB
7Accepted4ms820 KiB
8Accepted4ms872 KiB
9Accepted1ms316 KiB
10Accepted6ms1216 KiB
11Accepted1ms316 KiB
12Accepted1ms316 KiB
subtask30/25
13Wrong answer1ms316 KiB
14Accepted1ms316 KiB
15Wrong answer2ms316 KiB
16Wrong answer1ms316 KiB
17Accepted1ms316 KiB
18Runtime error412ms262144 KiB
19Runtime error421ms262144 KiB
20Runtime error529ms262144 KiB
21Runtime error522ms262144 KiB
22Runtime error522ms262144 KiB
23Runtime error414ms262144 KiB
24Runtime error503ms262144 KiB
25Runtime error405ms262144 KiB
26Runtime error460ms262144 KiB
27Runtime error412ms262144 KiB
28Runtime error405ms262144 KiB
29Runtime error513ms262144 KiB
30Runtime error521ms262144 KiB
31Runtime error409ms262144 KiB
32Runtime error402ms262144 KiB
33Runtime error512ms262144 KiB
subtask40/20
34Accepted1ms316 KiB
35Wrong answer1ms512 KiB
36Accepted1ms316 KiB
37Wrong answer1ms512 KiB
38Runtime error508ms262144 KiB
39Accepted1ms316 KiB
40Wrong answer1ms316 KiB
41Runtime error402ms262144 KiB
42Accepted1ms316 KiB
43Runtime error400ms262144 KiB
44Runtime error513ms262144 KiB
45Accepted2ms508 KiB
46Wrong answer1ms316 KiB
47Runtime error395ms262144 KiB
48Accepted1ms316 KiB
49Accepted1ms532 KiB
50Accepted1ms316 KiB
51Accepted1ms316 KiB
52Wrong answer1ms316 KiB
53Accepted1ms316 KiB
54Accepted1ms316 KiB
55Wrong answer1ms316 KiB
56Wrong answer1ms500 KiB
57Wrong answer1ms316 KiB
58Accepted1ms316 KiB
59Wrong answer1ms316 KiB
60Accepted1ms508 KiB
61Accepted1ms316 KiB
62Wrong answer1ms388 KiB
63Wrong answer1ms316 KiB
64Accepted1ms316 KiB
65Accepted1ms316 KiB
66Accepted1ms316 KiB
subtask50/15
67Accepted1ms316 KiB
68Accepted1ms316 KiB
69Accepted1ms316 KiB
70Accepted1ms500 KiB
71Accepted3ms636 KiB
72Accepted2ms316 KiB
73Accepted4ms820 KiB
74Accepted4ms872 KiB
75Accepted1ms316 KiB
76Accepted6ms1216 KiB
77Accepted1ms316 KiB
78Accepted1ms316 KiB
79Wrong answer1ms316 KiB
80Accepted1ms316 KiB
81Wrong answer2ms316 KiB
82Wrong answer1ms316 KiB
83Accepted1ms316 KiB
84Runtime error412ms262144 KiB
85Runtime error421ms262144 KiB
86Runtime error529ms262144 KiB
87Runtime error522ms262144 KiB
88Runtime error522ms262144 KiB
89Runtime error414ms262144 KiB
90Runtime error503ms262144 KiB
91Runtime error405ms262144 KiB
92Runtime error460ms262144 KiB
93Runtime error412ms262144 KiB
94Runtime error405ms262144 KiB
95Runtime error513ms262144 KiB
96Runtime error521ms262144 KiB
97Runtime error409ms262144 KiB
98Runtime error402ms262144 KiB
99Runtime error512ms262144 KiB
100Wrong answer1ms512 KiB
101Accepted1ms316 KiB
102Wrong answer1ms512 KiB
103Runtime error508ms262144 KiB
104Accepted1ms316 KiB
105Wrong answer1ms316 KiB
106Runtime error402ms262144 KiB
107Accepted1ms316 KiB
108Runtime error400ms262144 KiB
109Runtime error513ms262144 KiB
110Accepted2ms508 KiB
111Wrong answer1ms316 KiB
112Runtime error395ms262144 KiB
113Accepted1ms316 KiB
114Accepted1ms532 KiB
115Accepted1ms316 KiB
116Accepted1ms316 KiB
117Wrong answer1ms316 KiB
118Accepted1ms316 KiB
119Accepted1ms316 KiB
120Wrong answer1ms316 KiB
121Wrong answer1ms500 KiB
122Wrong answer1ms316 KiB
123Accepted1ms316 KiB
124Wrong answer1ms316 KiB
125Accepted1ms508 KiB
126Accepted1ms316 KiB
127Wrong answer1ms388 KiB
128Wrong answer1ms316 KiB
129Accepted1ms316 KiB
130Accepted1ms316 KiB
131Accepted1ms316 KiB
132Wrong answer1ms316 KiB
133Accepted2ms316 KiB
134Wrong answer1ms316 KiB
135Runtime error402ms262144 KiB
136Runtime error509ms262144 KiB
137Accepted1ms316 KiB
138Wrong answer1ms316 KiB
139Accepted2ms316 KiB
140Accepted3ms564 KiB
141Wrong answer2ms500 KiB
142Wrong answer4ms820 KiB
143Wrong answer4ms820 KiB
144Accepted4ms1084 KiB
145Wrong answer4ms820 KiB
146Accepted8ms1588 KiB
147Wrong answer8ms1336 KiB
148Wrong answer4ms876 KiB
149Wrong answer2ms564 KiB