229462026-01-16 09:24:23Leventusz09Városnézéscpp17Wrong answer 20/80698ms262144 KiB
#include <iostream>
#include <vector>
#include <stdint.h>

using namespace std;

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


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

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

    for(int32_t i=0; i<M; i++){
        int32_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<int32_t> q;
    q.push_back(0);
    int32_t si= 0;
    while(si < q.size()){
        for(int32_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<int32_t> o1;
    for(int32_t i=N - 1; i != 0; i = terek[i].ob){
        o1.push_back(i+1);
        if(i == -1){
            cout << -1 << endl;
            return 0;
        }
    }
    cout << 1 << " ";
    for(int32_t i = o1.size()-1; i >= 0; i--) cout << o1[i] << " "; 
    cout << endl;

    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms1076 KiB
subtask220/20
2Accepted2ms1076 KiB
3Accepted2ms1076 KiB
4Accepted2ms1076 KiB
5Accepted4ms1332 KiB
6Accepted3ms1216 KiB
7Accepted8ms1432 KiB
8Accepted8ms1232 KiB
9Accepted1ms1076 KiB
10Accepted14ms1696 KiB
11Accepted2ms1076 KiB
12Accepted1ms1076 KiB
subtask30/25
13Accepted2ms1272 KiB
14Accepted2ms1268 KiB
15Accepted2ms1076 KiB
16Accepted3ms1456 KiB
17Accepted2ms1076 KiB
18Accepted2ms1076 KiB
19Accepted2ms1152 KiB
20Wrong answer1ms1076 KiB
21Wrong answer2ms1260 KiB
22Runtime error441ms262144 KiB
23Wrong answer2ms1076 KiB
24Runtime error448ms262144 KiB
25Accepted27ms9432 KiB
26Wrong answer3ms1076 KiB
27Wrong answer4ms1076 KiB
28Runtime error600ms262144 KiB
29Accepted14ms5280 KiB
30Runtime error586ms262144 KiB
31Wrong answer16ms1076 KiB
32Wrong answer32ms1332 KiB
33Wrong answer9ms1076 KiB
subtask40/20
34Accepted2ms1268 KiB
35Accepted2ms1268 KiB
36Accepted1ms1076 KiB
37Accepted1ms1076 KiB
38Accepted2ms1456 KiB
39Accepted1ms1076 KiB
40Accepted2ms1076 KiB
41Wrong answer2ms1076 KiB
42Wrong answer2ms1076 KiB
43Wrong answer1ms1076 KiB
44Accepted2ms1468 KiB
45Wrong answer2ms1076 KiB
46Accepted6ms3324 KiB
47Accepted2ms1076 KiB
48Wrong answer2ms1076 KiB
49Wrong answer2ms1076 KiB
50Accepted2ms1076 KiB
51Accepted2ms1076 KiB
52Accepted1ms1076 KiB
53Accepted2ms1076 KiB
54Accepted2ms1076 KiB
55Accepted2ms1028 KiB
56Accepted1ms1076 KiB
57Accepted2ms1076 KiB
58Accepted2ms992 KiB
59Accepted1ms1076 KiB
60Accepted1ms1268 KiB
61Accepted2ms968 KiB
62Accepted2ms1076 KiB
63Accepted2ms1076 KiB
64Accepted2ms1076 KiB
65Accepted2ms1076 KiB
66Accepted2ms1076 KiB
subtask50/15
67Accepted2ms1268 KiB
68Accepted2ms1076 KiB
69Accepted2ms1076 KiB
70Accepted2ms1076 KiB
71Accepted4ms1332 KiB
72Accepted3ms1216 KiB
73Accepted8ms1432 KiB
74Accepted8ms1232 KiB
75Accepted1ms1076 KiB
76Accepted14ms1696 KiB
77Accepted2ms1076 KiB
78Accepted1ms1076 KiB
79Accepted2ms1272 KiB
80Accepted2ms1268 KiB
81Accepted2ms1076 KiB
82Accepted3ms1456 KiB
83Accepted2ms1076 KiB
84Accepted2ms1076 KiB
85Accepted2ms1152 KiB
86Wrong answer1ms1076 KiB
87Wrong answer2ms1260 KiB
88Runtime error441ms262144 KiB
89Wrong answer2ms1076 KiB
90Runtime error448ms262144 KiB
91Accepted27ms9432 KiB
92Wrong answer3ms1076 KiB
93Wrong answer4ms1076 KiB
94Runtime error600ms262144 KiB
95Accepted14ms5280 KiB
96Runtime error586ms262144 KiB
97Wrong answer16ms1076 KiB
98Wrong answer32ms1332 KiB
99Wrong answer9ms1076 KiB
100Accepted2ms1268 KiB
101Accepted1ms1076 KiB
102Accepted1ms1076 KiB
103Accepted2ms1456 KiB
104Accepted1ms1076 KiB
105Accepted2ms1076 KiB
106Wrong answer2ms1076 KiB
107Wrong answer2ms1076 KiB
108Wrong answer1ms1076 KiB
109Accepted2ms1468 KiB
110Wrong answer2ms1076 KiB
111Accepted6ms3324 KiB
112Accepted2ms1076 KiB
113Wrong answer2ms1076 KiB
114Wrong answer2ms1076 KiB
115Accepted2ms1076 KiB
116Accepted2ms1076 KiB
117Accepted1ms1076 KiB
118Accepted2ms1076 KiB
119Accepted2ms1076 KiB
120Accepted2ms1028 KiB
121Accepted1ms1076 KiB
122Accepted2ms1076 KiB
123Accepted2ms992 KiB
124Accepted1ms1076 KiB
125Accepted1ms1268 KiB
126Accepted2ms968 KiB
127Accepted2ms1076 KiB
128Accepted2ms1076 KiB
129Accepted2ms1076 KiB
130Accepted2ms1076 KiB
131Accepted2ms1076 KiB
132Runtime error551ms262144 KiB
133Wrong answer2ms1076 KiB
134Runtime error570ms262144 KiB
135Accepted388ms132596 KiB
136Runtime error458ms262144 KiB
137Wrong answer4ms2220 KiB
138Runtime error526ms262144 KiB
139Wrong answer3ms1076 KiB
140Accepted4ms1332 KiB
141Accepted3ms1076 KiB
142Accepted9ms1332 KiB
143Accepted14ms2480 KiB
144Accepted10ms1432 KiB
145Accepted8ms1616 KiB
146Accepted20ms1956 KiB
147Runtime error602ms262144 KiB
148Runtime error698ms262144 KiB
149Runtime error536ms262144 KiB