199932025-12-30 21:52:47VargaVivienVárosnézéscpp17Time limit exceeded 20/801.11s262144 KiB
#include <iostream>
#include <vector>
#include <string>

using namespace std;

struct ut
{
    int bol, ba;
};

bool latogatas(int varos, int *latvanyossag, int *db, vector<vector<int>> terkep, int n, vector<int> &szam)
{
    bool vege = false;
    vector<int> maximum;
    vector<int> temp;
    int maxi = 0;
   // cout << "szam" << &szam << endl;
   // cout << "temp" << &temp << endl;
    if(varos == n)
    {
        vege = true;
        *db += latvanyossag[varos - 1];
        szam.push_back(varos);
        return vege;
    }
    else
    {
        int reszdb;
        //szam.push_back(varos);
        for(int i = 0; i < terkep[varos].size(); i++)
        {

            reszdb = *db + latvanyossag[varos - 1];
            temp.clear();

                if(latogatas(terkep[varos][i], latvanyossag, &reszdb, terkep, n, temp))
                {
                    vege = true;
                    if(reszdb > maxi)
                    {
                        maxi = reszdb;
                        maximum.clear();
                        maximum=temp;
                    }
                }

        }
        if(!vege)
        {
            szam.pop_back();
        }
        else
        {
            //szam.insert(szam.end(), maximum.begin(), maximum.end());
            szam=maximum;
            szam.push_back(varos);

        }
        *db = maxi;
        return vege;
    }
}

int main()
{
    int n, m;
    ut x;
    cin >> x.bol >> x.ba;
    n = x.bol;
    m = x.ba;
    int numbers[n];
    for(int i=0; i<n; i++) cin >> numbers[i];

    vector <vector<int>> terkep(n+1);

    for(int i = 0; i < m; i++)
    {
        cin >> x.bol >> x.ba;
        terkep[x.bol].push_back(x.ba);

    }
    int db = 0;
    vector<int> szam;
    if (latogatas(1, numbers, &db, terkep, n, szam))
    {
        cout << db << endl;
        //cout << szam.size()<< endl;
        for (int j=szam.size()-1; j>=0;j--)
        {
            cout << szam[j] << " ";
        }
    }
    else
    {
        cout << -1 << endl;
    }
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
subtask20/20
2Accepted2ms316 KiB
3Accepted2ms396 KiB
4Accepted2ms316 KiB
5Time limit exceeded1.09s6232 KiB
6Accepted190ms2924 KiB
7Time limit exceeded1.101s37636 KiB
8Time limit exceeded1.1s37140 KiB
9Accepted1ms316 KiB
10Runtime error347ms262144 KiB
11Accepted1ms316 KiB
12Accepted1ms316 KiB
subtask30/25
13Accepted1ms508 KiB
14Accepted1ms316 KiB
15Accepted1ms508 KiB
16Accepted32ms508 KiB
17Accepted1ms316 KiB
18Accepted6ms316 KiB
19Accepted1ms508 KiB
20Accepted1ms316 KiB
21Accepted1ms316 KiB
22Time limit exceeded1.1s912 KiB
23Accepted2ms316 KiB
24Time limit exceeded1.1s1152 KiB
25Time limit exceeded1.1s768 KiB
26Accepted2ms316 KiB
27Accepted4ms400 KiB
28Time limit exceeded1.1s6456 KiB
29Time limit exceeded1.083s2148 KiB
30Time limit exceeded1.1s8896 KiB
31Accepted17ms1340 KiB
32Accepted35ms1344 KiB
33Accepted10ms1332 KiB
subtask420/20
34Accepted1ms316 KiB
35Accepted1ms316 KiB
36Accepted2ms316 KiB
37Accepted1ms508 KiB
38Accepted14ms332 KiB
39Accepted1ms324 KiB
40Accepted6ms412 KiB
41Accepted1ms508 KiB
42Accepted1ms316 KiB
43Accepted1ms508 KiB
44Accepted16ms416 KiB
45Accepted1ms508 KiB
46Accepted284ms428 KiB
47Accepted3ms332 KiB
48Accepted1ms316 KiB
49Accepted4ms552 KiB
50Accepted1ms316 KiB
51Accepted1ms316 KiB
52Accepted1ms324 KiB
53Accepted1ms500 KiB
54Accepted1ms316 KiB
55Accepted1ms316 KiB
56Accepted1ms316 KiB
57Accepted1ms508 KiB
58Accepted1ms508 KiB
59Accepted1ms500 KiB
60Accepted1ms316 KiB
61Accepted1ms500 KiB
62Accepted1ms400 KiB
63Accepted1ms316 KiB
64Accepted1ms500 KiB
65Accepted1ms508 KiB
66Accepted1ms316 KiB
subtask50/15
67Accepted1ms316 KiB
68Accepted2ms316 KiB
69Accepted2ms396 KiB
70Accepted2ms316 KiB
71Time limit exceeded1.09s6232 KiB
72Accepted190ms2924 KiB
73Time limit exceeded1.101s37636 KiB
74Time limit exceeded1.1s37140 KiB
75Accepted1ms316 KiB
76Runtime error347ms262144 KiB
77Accepted1ms316 KiB
78Accepted1ms316 KiB
79Accepted1ms508 KiB
80Accepted1ms316 KiB
81Accepted1ms508 KiB
82Accepted32ms508 KiB
83Accepted1ms316 KiB
84Accepted6ms316 KiB
85Accepted1ms508 KiB
86Accepted1ms316 KiB
87Accepted1ms316 KiB
88Time limit exceeded1.1s912 KiB
89Accepted2ms316 KiB
90Time limit exceeded1.1s1152 KiB
91Time limit exceeded1.1s768 KiB
92Accepted2ms316 KiB
93Accepted4ms400 KiB
94Time limit exceeded1.1s6456 KiB
95Time limit exceeded1.083s2148 KiB
96Time limit exceeded1.1s8896 KiB
97Accepted17ms1340 KiB
98Accepted35ms1344 KiB
99Accepted10ms1332 KiB
100Accepted1ms316 KiB
101Accepted2ms316 KiB
102Accepted1ms508 KiB
103Accepted14ms332 KiB
104Accepted1ms324 KiB
105Accepted6ms412 KiB
106Accepted1ms508 KiB
107Accepted1ms316 KiB
108Accepted1ms508 KiB
109Accepted16ms416 KiB
110Accepted1ms508 KiB
111Accepted284ms428 KiB
112Accepted3ms332 KiB
113Accepted1ms316 KiB
114Accepted4ms552 KiB
115Accepted1ms316 KiB
116Accepted1ms316 KiB
117Accepted1ms324 KiB
118Accepted1ms500 KiB
119Accepted1ms316 KiB
120Accepted1ms316 KiB
121Accepted1ms316 KiB
122Accepted1ms508 KiB
123Accepted1ms508 KiB
124Accepted1ms500 KiB
125Accepted1ms316 KiB
126Accepted1ms500 KiB
127Accepted1ms400 KiB
128Accepted1ms316 KiB
129Accepted1ms500 KiB
130Accepted1ms508 KiB
131Accepted1ms316 KiB
132Time limit exceeded1.072s1012 KiB
133Accepted2ms316 KiB
134Time limit exceeded1.074s1324 KiB
135Time limit exceeded1.074s820 KiB
136Time limit exceeded1.1s808 KiB
137Time limit exceeded1.092s756 KiB
138Time limit exceeded1.092s724 KiB
139Accepted3ms356 KiB
140Time limit exceeded1.1s6280 KiB
141Accepted697ms15412 KiB
142Time limit exceeded1.08s15564 KiB
143Time limit exceeded1.087s57876 KiB
144Time limit exceeded1.085s48140 KiB
145Time limit exceeded1.11s166396 KiB
146Time limit exceeded1.088s83576 KiB
147Runtime error546ms262144 KiB
148Time limit exceeded1.092s179308 KiB
149Runtime error379ms262144 KiB