229282026-01-16 09:06:33Leventusz09Városnézéscpp17Wrong answer 20/80717ms262144 KiB
#include <iostream>
#include <vector>
#include <stdint.h>

using namespace std;

struct Ter {
    vector<uint32_t> et;
    //vector<uint32_t> ef;
    uint32_t n;  // látványosságok száma
    uint32_t an = 0; // sok látványosság
    uint32_t ob; // előző elem
};


int main(){
    Ter terek[20'000];
    uint32_t N, M;
    cin >> N >> M;

    for(uint32_t i=0; i<N; i++) cin >> terek[i].n;

    for(uint32_t i=0; i<M; i++){
        uint32_t t1, t2;
        cin >> t1 >> t2;
        terek[t1-1].et.push_back(t2-1);
        //terek[t2-1].ef.push_back(t1-1);
    }

    terek[0].an = terek[0].n;
    vector<uint32_t> q;
    q.push_back(0);
    uint32_t si= 0;
    while(si < q.size()){
        for(uint32_t&x:terek[q[si]].et){
            q.push_back(x);
            if(terek[x].an < terek[q[si]].an + terek[x].n) {
                terek[x].an = terek[q[si]].an + terek[x].n;
                terek[x].ob = q[si];
            }
        }
        si++;
    }

    cout << terek[N - 1].an << endl;
    vector<uint32_t> o1;
    for(uint32_t i=N - 1; i != 0; i = terek[i].ob) o1.push_back(i+1);
    cout << 1 << " ";
    for(int32_t i = o1.size()-1; i >= 0; i--) cout << o1[i] << " ";
    cout << endl;

    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted2ms1144 KiB
subtask220/20
2Accepted2ms1076 KiB
3Accepted2ms1260 KiB
4Accepted2ms1076 KiB
5Accepted6ms1332 KiB
6Accepted4ms1076 KiB
7Accepted8ms1440 KiB
8Accepted8ms1244 KiB
9Accepted2ms1076 KiB
10Accepted14ms1684 KiB
11Accepted2ms1080 KiB
12Accepted2ms1144 KiB
subtask30/25
13Accepted2ms1092 KiB
14Accepted2ms1260 KiB
15Accepted2ms1260 KiB
16Accepted2ms1456 KiB
17Accepted2ms1080 KiB
18Accepted2ms1080 KiB
19Accepted1ms988 KiB
20Wrong answer2ms1076 KiB
21Wrong answer2ms1084 KiB
22Runtime error589ms262144 KiB
23Wrong answer2ms1076 KiB
24Runtime error490ms262144 KiB
25Accepted25ms9452 KiB
26Wrong answer3ms1076 KiB
27Wrong answer4ms1076 KiB
28Runtime error529ms262144 KiB
29Accepted14ms5280 KiB
30Runtime error629ms262144 KiB
31Wrong answer16ms1316 KiB
32Wrong answer32ms1332 KiB
33Wrong answer9ms1092 KiB
subtask40/20
34Accepted2ms1076 KiB
35Accepted1ms1080 KiB
36Accepted2ms1076 KiB
37Accepted1ms1076 KiB
38Accepted2ms1456 KiB
39Accepted1ms1268 KiB
40Accepted2ms1076 KiB
41Wrong answer1ms1076 KiB
42Wrong answer2ms1268 KiB
43Wrong answer2ms1084 KiB
44Accepted3ms1456 KiB
45Wrong answer2ms1076 KiB
46Accepted7ms3240 KiB
47Accepted2ms1076 KiB
48Wrong answer2ms1076 KiB
49Wrong answer2ms1184 KiB
50Accepted2ms1080 KiB
51Accepted2ms1076 KiB
52Accepted1ms1076 KiB
53Accepted1ms1076 KiB
54Accepted2ms1076 KiB
55Accepted2ms1076 KiB
56Accepted1ms1080 KiB
57Accepted1ms1076 KiB
58Accepted2ms1260 KiB
59Accepted2ms1076 KiB
60Accepted1ms1076 KiB
61Accepted1ms1260 KiB
62Accepted2ms1076 KiB
63Accepted1ms968 KiB
64Accepted2ms1076 KiB
65Accepted1ms1076 KiB
66Accepted1ms1076 KiB
subtask50/15
67Accepted2ms1076 KiB
68Accepted2ms1076 KiB
69Accepted2ms1260 KiB
70Accepted2ms1076 KiB
71Accepted6ms1332 KiB
72Accepted4ms1076 KiB
73Accepted8ms1440 KiB
74Accepted8ms1244 KiB
75Accepted2ms1076 KiB
76Accepted14ms1684 KiB
77Accepted2ms1080 KiB
78Accepted2ms1144 KiB
79Accepted2ms1092 KiB
80Accepted2ms1260 KiB
81Accepted2ms1260 KiB
82Accepted2ms1456 KiB
83Accepted2ms1080 KiB
84Accepted2ms1080 KiB
85Accepted1ms988 KiB
86Wrong answer2ms1076 KiB
87Wrong answer2ms1084 KiB
88Runtime error589ms262144 KiB
89Wrong answer2ms1076 KiB
90Runtime error490ms262144 KiB
91Accepted25ms9452 KiB
92Wrong answer3ms1076 KiB
93Wrong answer4ms1076 KiB
94Runtime error529ms262144 KiB
95Accepted14ms5280 KiB
96Runtime error629ms262144 KiB
97Wrong answer16ms1316 KiB
98Wrong answer32ms1332 KiB
99Wrong answer9ms1092 KiB
100Accepted1ms1080 KiB
101Accepted2ms1076 KiB
102Accepted1ms1076 KiB
103Accepted2ms1456 KiB
104Accepted1ms1268 KiB
105Accepted2ms1076 KiB
106Wrong answer1ms1076 KiB
107Wrong answer2ms1268 KiB
108Wrong answer2ms1084 KiB
109Accepted3ms1456 KiB
110Wrong answer2ms1076 KiB
111Accepted7ms3240 KiB
112Accepted2ms1076 KiB
113Wrong answer2ms1076 KiB
114Wrong answer2ms1184 KiB
115Accepted2ms1080 KiB
116Accepted2ms1076 KiB
117Accepted1ms1076 KiB
118Accepted1ms1076 KiB
119Accepted2ms1076 KiB
120Accepted2ms1076 KiB
121Accepted1ms1080 KiB
122Accepted1ms1076 KiB
123Accepted2ms1260 KiB
124Accepted2ms1076 KiB
125Accepted1ms1076 KiB
126Accepted1ms1260 KiB
127Accepted2ms1076 KiB
128Accepted1ms968 KiB
129Accepted2ms1076 KiB
130Accepted1ms1076 KiB
131Accepted1ms1076 KiB
132Runtime error583ms262144 KiB
133Wrong answer3ms1096 KiB
134Runtime error504ms262144 KiB
135Accepted405ms132672 KiB
136Runtime error540ms262144 KiB
137Wrong answer4ms2220 KiB
138Runtime error451ms262144 KiB
139Wrong answer3ms1076 KiB
140Accepted6ms1332 KiB
141Accepted4ms1244 KiB
142Accepted8ms1332 KiB
143Accepted14ms2572 KiB
144Accepted12ms1588 KiB
145Accepted8ms1588 KiB
146Accepted20ms1908 KiB
147Runtime error717ms262144 KiB
148Runtime error620ms262144 KiB
149Runtime error674ms262144 KiB