199842025-12-30 21:09:32VargaVivienVárosnézéscpp17Runtime error 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 = 1; i <= n; i++)
        {

            reszdb = *db + latvanyossag[varos - 1];
            temp.clear();
            if(terkep[varos-1][i-1] == 1)
            {
                if(latogatas(i, latvanyossag, &reszdb, terkep, n, temp))
                {
                    vege = true;
                    if(reszdb > maxi)
                    {
                        maxi = reszdb;
                        maximum.clear();
                        for(int j : temp)
                        {
                        //    cout << temp[j] <<endl;
                            maximum.push_back(j);
                        }
                    }
                }
            }
        }
        if(!vege)
        {
            szam.pop_back();
        }
        else
        {
            for(int j:maximum)
            {
                szam.push_back(j);
            }
        }
        *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, vector<int>(n,0));

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

    }
    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)
        {
            cout << j << " ";
        }
    }
    else
    {
        cout << -1 << endl;
    }
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
subtask20/20
2Accepted1ms316 KiB
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Runtime error280ms262144 KiB
6Runtime error425ms262144 KiB
7Runtime error263ms262144 KiB
8Runtime error222ms262144 KiB
9Accepted2ms820 KiB
10Runtime error219ms262144 KiB
11Accepted1ms564 KiB
12Accepted1ms316 KiB
subtask30/25
13Accepted1ms316 KiB
14Accepted1ms500 KiB
15Accepted1ms316 KiB
16Accepted37ms316 KiB
17Accepted1ms316 KiB
18Accepted10ms316 KiB
19Accepted1ms316 KiB
20Accepted1ms500 KiB
21Accepted1ms508 KiB
22Time limit exceeded1.1s12796 KiB
23Accepted32ms30604 KiB
24Time limit exceeded1.1s19468 KiB
25Time limit exceeded1.1s17148 KiB
26Accepted14ms13108 KiB
27Accepted24ms21052 KiB
28Runtime error301ms262144 KiB
29Time limit exceeded1.11s262144 KiB
30Runtime error237ms262144 KiB
31Runtime error226ms262144 KiB
32Runtime error257ms262144 KiB
33Runtime error215ms262144 KiB
subtask420/20
34Accepted1ms536 KiB
35Accepted1ms512 KiB
36Accepted1ms316 KiB
37Accepted1ms316 KiB
38Accepted18ms432 KiB
39Accepted1ms316 KiB
40Accepted9ms316 KiB
41Accepted1ms316 KiB
42Accepted1ms316 KiB
43Accepted1ms316 KiB
44Accepted18ms508 KiB
45Accepted1ms316 KiB
46Accepted563ms732 KiB
47Accepted4ms448 KiB
48Accepted1ms316 KiB
49Accepted4ms748 KiB
50Accepted1ms508 KiB
51Accepted1ms316 KiB
52Accepted1ms380 KiB
53Accepted1ms316 KiB
54Accepted1ms324 KiB
55Accepted1ms316 KiB
56Accepted1ms404 KiB
57Accepted1ms316 KiB
58Accepted1ms564 KiB
59Accepted1ms500 KiB
60Accepted1ms328 KiB
61Accepted1ms316 KiB
62Accepted1ms508 KiB
63Accepted1ms316 KiB
64Accepted1ms508 KiB
65Accepted1ms316 KiB
66Accepted2ms516 KiB
subtask50/15
67Accepted1ms536 KiB
68Accepted1ms316 KiB
69Accepted1ms316 KiB
70Accepted1ms316 KiB
71Runtime error280ms262144 KiB
72Runtime error425ms262144 KiB
73Runtime error263ms262144 KiB
74Runtime error222ms262144 KiB
75Accepted2ms820 KiB
76Runtime error219ms262144 KiB
77Accepted1ms564 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms500 KiB
81Accepted1ms316 KiB
82Accepted37ms316 KiB
83Accepted1ms316 KiB
84Accepted10ms316 KiB
85Accepted1ms316 KiB
86Accepted1ms500 KiB
87Accepted1ms508 KiB
88Time limit exceeded1.1s12796 KiB
89Accepted32ms30604 KiB
90Time limit exceeded1.1s19468 KiB
91Time limit exceeded1.1s17148 KiB
92Accepted14ms13108 KiB
93Accepted24ms21052 KiB
94Runtime error301ms262144 KiB
95Time limit exceeded1.11s262144 KiB
96Runtime error237ms262144 KiB
97Runtime error226ms262144 KiB
98Runtime error257ms262144 KiB
99Runtime error215ms262144 KiB
100Accepted1ms512 KiB
101Accepted1ms316 KiB
102Accepted1ms316 KiB
103Accepted18ms432 KiB
104Accepted1ms316 KiB
105Accepted9ms316 KiB
106Accepted1ms316 KiB
107Accepted1ms316 KiB
108Accepted1ms316 KiB
109Accepted18ms508 KiB
110Accepted1ms316 KiB
111Accepted563ms732 KiB
112Accepted4ms448 KiB
113Accepted1ms316 KiB
114Accepted4ms748 KiB
115Accepted1ms508 KiB
116Accepted1ms316 KiB
117Accepted1ms380 KiB
118Accepted1ms316 KiB
119Accepted1ms324 KiB
120Accepted1ms316 KiB
121Accepted1ms404 KiB
122Accepted1ms316 KiB
123Accepted1ms564 KiB
124Accepted1ms500 KiB
125Accepted1ms328 KiB
126Accepted1ms316 KiB
127Accepted1ms508 KiB
128Accepted1ms316 KiB
129Accepted1ms508 KiB
130Accepted1ms316 KiB
131Accepted2ms516 KiB
132Time limit exceeded1.075s6268 KiB
133Accepted32ms30516 KiB
134Time limit exceeded1.078s16428 KiB
135Time limit exceeded1.077s20924 KiB
136Time limit exceeded1.075s16700 KiB
137Time limit exceeded1.082s17208 KiB
138Time limit exceeded1.08s4400 KiB
139Accepted32ms31028 KiB
140Runtime error268ms262144 KiB
141Runtime error200ms262144 KiB
142Runtime error221ms262144 KiB
143Runtime error261ms262144 KiB
144Runtime error252ms262144 KiB
145Runtime error224ms262144 KiB
146Runtime error263ms262144 KiB
147Runtime error211ms262144 KiB
148Runtime error259ms262144 KiB
149Runtime error275ms262144 KiB