199842025-12-30 21:09:32VargaVivienVárosnézéscpp17Futási hiba 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
subtask20/20
2Elfogadva1ms316 KiB
3Elfogadva1ms316 KiB
4Elfogadva1ms316 KiB
5Futási hiba280ms262144 KiB
6Futási hiba425ms262144 KiB
7Futási hiba263ms262144 KiB
8Futási hiba222ms262144 KiB
9Elfogadva2ms820 KiB
10Futási hiba219ms262144 KiB
11Elfogadva1ms564 KiB
12Elfogadva1ms316 KiB
subtask30/25
13Elfogadva1ms316 KiB
14Elfogadva1ms500 KiB
15Elfogadva1ms316 KiB
16Elfogadva37ms316 KiB
17Elfogadva1ms316 KiB
18Elfogadva10ms316 KiB
19Elfogadva1ms316 KiB
20Elfogadva1ms500 KiB
21Elfogadva1ms508 KiB
22Időlimit túllépés1.1s12796 KiB
23Elfogadva32ms30604 KiB
24Időlimit túllépés1.1s19468 KiB
25Időlimit túllépés1.1s17148 KiB
26Elfogadva14ms13108 KiB
27Elfogadva24ms21052 KiB
28Futási hiba301ms262144 KiB
29Időlimit túllépés1.11s262144 KiB
30Futási hiba237ms262144 KiB
31Futási hiba226ms262144 KiB
32Futási hiba257ms262144 KiB
33Futási hiba215ms262144 KiB
subtask420/20
34Elfogadva1ms536 KiB
35Elfogadva1ms512 KiB
36Elfogadva1ms316 KiB
37Elfogadva1ms316 KiB
38Elfogadva18ms432 KiB
39Elfogadva1ms316 KiB
40Elfogadva9ms316 KiB
41Elfogadva1ms316 KiB
42Elfogadva1ms316 KiB
43Elfogadva1ms316 KiB
44Elfogadva18ms508 KiB
45Elfogadva1ms316 KiB
46Elfogadva563ms732 KiB
47Elfogadva4ms448 KiB
48Elfogadva1ms316 KiB
49Elfogadva4ms748 KiB
50Elfogadva1ms508 KiB
51Elfogadva1ms316 KiB
52Elfogadva1ms380 KiB
53Elfogadva1ms316 KiB
54Elfogadva1ms324 KiB
55Elfogadva1ms316 KiB
56Elfogadva1ms404 KiB
57Elfogadva1ms316 KiB
58Elfogadva1ms564 KiB
59Elfogadva1ms500 KiB
60Elfogadva1ms328 KiB
61Elfogadva1ms316 KiB
62Elfogadva1ms508 KiB
63Elfogadva1ms316 KiB
64Elfogadva1ms508 KiB
65Elfogadva1ms316 KiB
66Elfogadva2ms516 KiB
subtask50/15
67Elfogadva1ms536 KiB
68Elfogadva1ms316 KiB
69Elfogadva1ms316 KiB
70Elfogadva1ms316 KiB
71Futási hiba280ms262144 KiB
72Futási hiba425ms262144 KiB
73Futási hiba263ms262144 KiB
74Futási hiba222ms262144 KiB
75Elfogadva2ms820 KiB
76Futási hiba219ms262144 KiB
77Elfogadva1ms564 KiB
78Elfogadva1ms316 KiB
79Elfogadva1ms316 KiB
80Elfogadva1ms500 KiB
81Elfogadva1ms316 KiB
82Elfogadva37ms316 KiB
83Elfogadva1ms316 KiB
84Elfogadva10ms316 KiB
85Elfogadva1ms316 KiB
86Elfogadva1ms500 KiB
87Elfogadva1ms508 KiB
88Időlimit túllépés1.1s12796 KiB
89Elfogadva32ms30604 KiB
90Időlimit túllépés1.1s19468 KiB
91Időlimit túllépés1.1s17148 KiB
92Elfogadva14ms13108 KiB
93Elfogadva24ms21052 KiB
94Futási hiba301ms262144 KiB
95Időlimit túllépés1.11s262144 KiB
96Futási hiba237ms262144 KiB
97Futási hiba226ms262144 KiB
98Futási hiba257ms262144 KiB
99Futási hiba215ms262144 KiB
100Elfogadva1ms512 KiB
101Elfogadva1ms316 KiB
102Elfogadva1ms316 KiB
103Elfogadva18ms432 KiB
104Elfogadva1ms316 KiB
105Elfogadva9ms316 KiB
106Elfogadva1ms316 KiB
107Elfogadva1ms316 KiB
108Elfogadva1ms316 KiB
109Elfogadva18ms508 KiB
110Elfogadva1ms316 KiB
111Elfogadva563ms732 KiB
112Elfogadva4ms448 KiB
113Elfogadva1ms316 KiB
114Elfogadva4ms748 KiB
115Elfogadva1ms508 KiB
116Elfogadva1ms316 KiB
117Elfogadva1ms380 KiB
118Elfogadva1ms316 KiB
119Elfogadva1ms324 KiB
120Elfogadva1ms316 KiB
121Elfogadva1ms404 KiB
122Elfogadva1ms316 KiB
123Elfogadva1ms564 KiB
124Elfogadva1ms500 KiB
125Elfogadva1ms328 KiB
126Elfogadva1ms316 KiB
127Elfogadva1ms508 KiB
128Elfogadva1ms316 KiB
129Elfogadva1ms508 KiB
130Elfogadva1ms316 KiB
131Elfogadva2ms516 KiB
132Időlimit túllépés1.075s6268 KiB
133Elfogadva32ms30516 KiB
134Időlimit túllépés1.078s16428 KiB
135Időlimit túllépés1.077s20924 KiB
136Időlimit túllépés1.075s16700 KiB
137Időlimit túllépés1.082s17208 KiB
138Időlimit túllépés1.08s4400 KiB
139Elfogadva32ms31028 KiB
140Futási hiba268ms262144 KiB
141Futási hiba200ms262144 KiB
142Futási hiba221ms262144 KiB
143Futási hiba261ms262144 KiB
144Futási hiba252ms262144 KiB
145Futási hiba224ms262144 KiB
146Futási hiba263ms262144 KiB
147Futási hiba211ms262144 KiB
148Futási hiba259ms262144 KiB
149Futási hiba275ms262144 KiB