199932025-12-30 21:52:47VargaVivienVárosnézéscpp17Időlimit túllépés 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
subtask20/20
2Elfogadva2ms316 KiB
3Elfogadva2ms396 KiB
4Elfogadva2ms316 KiB
5Időlimit túllépés1.09s6232 KiB
6Elfogadva190ms2924 KiB
7Időlimit túllépés1.101s37636 KiB
8Időlimit túllépés1.1s37140 KiB
9Elfogadva1ms316 KiB
10Futási hiba347ms262144 KiB
11Elfogadva1ms316 KiB
12Elfogadva1ms316 KiB
subtask30/25
13Elfogadva1ms508 KiB
14Elfogadva1ms316 KiB
15Elfogadva1ms508 KiB
16Elfogadva32ms508 KiB
17Elfogadva1ms316 KiB
18Elfogadva6ms316 KiB
19Elfogadva1ms508 KiB
20Elfogadva1ms316 KiB
21Elfogadva1ms316 KiB
22Időlimit túllépés1.1s912 KiB
23Elfogadva2ms316 KiB
24Időlimit túllépés1.1s1152 KiB
25Időlimit túllépés1.1s768 KiB
26Elfogadva2ms316 KiB
27Elfogadva4ms400 KiB
28Időlimit túllépés1.1s6456 KiB
29Időlimit túllépés1.083s2148 KiB
30Időlimit túllépés1.1s8896 KiB
31Elfogadva17ms1340 KiB
32Elfogadva35ms1344 KiB
33Elfogadva10ms1332 KiB
subtask420/20
34Elfogadva1ms316 KiB
35Elfogadva1ms316 KiB
36Elfogadva2ms316 KiB
37Elfogadva1ms508 KiB
38Elfogadva14ms332 KiB
39Elfogadva1ms324 KiB
40Elfogadva6ms412 KiB
41Elfogadva1ms508 KiB
42Elfogadva1ms316 KiB
43Elfogadva1ms508 KiB
44Elfogadva16ms416 KiB
45Elfogadva1ms508 KiB
46Elfogadva284ms428 KiB
47Elfogadva3ms332 KiB
48Elfogadva1ms316 KiB
49Elfogadva4ms552 KiB
50Elfogadva1ms316 KiB
51Elfogadva1ms316 KiB
52Elfogadva1ms324 KiB
53Elfogadva1ms500 KiB
54Elfogadva1ms316 KiB
55Elfogadva1ms316 KiB
56Elfogadva1ms316 KiB
57Elfogadva1ms508 KiB
58Elfogadva1ms508 KiB
59Elfogadva1ms500 KiB
60Elfogadva1ms316 KiB
61Elfogadva1ms500 KiB
62Elfogadva1ms400 KiB
63Elfogadva1ms316 KiB
64Elfogadva1ms500 KiB
65Elfogadva1ms508 KiB
66Elfogadva1ms316 KiB
subtask50/15
67Elfogadva1ms316 KiB
68Elfogadva2ms316 KiB
69Elfogadva2ms396 KiB
70Elfogadva2ms316 KiB
71Időlimit túllépés1.09s6232 KiB
72Elfogadva190ms2924 KiB
73Időlimit túllépés1.101s37636 KiB
74Időlimit túllépés1.1s37140 KiB
75Elfogadva1ms316 KiB
76Futási hiba347ms262144 KiB
77Elfogadva1ms316 KiB
78Elfogadva1ms316 KiB
79Elfogadva1ms508 KiB
80Elfogadva1ms316 KiB
81Elfogadva1ms508 KiB
82Elfogadva32ms508 KiB
83Elfogadva1ms316 KiB
84Elfogadva6ms316 KiB
85Elfogadva1ms508 KiB
86Elfogadva1ms316 KiB
87Elfogadva1ms316 KiB
88Időlimit túllépés1.1s912 KiB
89Elfogadva2ms316 KiB
90Időlimit túllépés1.1s1152 KiB
91Időlimit túllépés1.1s768 KiB
92Elfogadva2ms316 KiB
93Elfogadva4ms400 KiB
94Időlimit túllépés1.1s6456 KiB
95Időlimit túllépés1.083s2148 KiB
96Időlimit túllépés1.1s8896 KiB
97Elfogadva17ms1340 KiB
98Elfogadva35ms1344 KiB
99Elfogadva10ms1332 KiB
100Elfogadva1ms316 KiB
101Elfogadva2ms316 KiB
102Elfogadva1ms508 KiB
103Elfogadva14ms332 KiB
104Elfogadva1ms324 KiB
105Elfogadva6ms412 KiB
106Elfogadva1ms508 KiB
107Elfogadva1ms316 KiB
108Elfogadva1ms508 KiB
109Elfogadva16ms416 KiB
110Elfogadva1ms508 KiB
111Elfogadva284ms428 KiB
112Elfogadva3ms332 KiB
113Elfogadva1ms316 KiB
114Elfogadva4ms552 KiB
115Elfogadva1ms316 KiB
116Elfogadva1ms316 KiB
117Elfogadva1ms324 KiB
118Elfogadva1ms500 KiB
119Elfogadva1ms316 KiB
120Elfogadva1ms316 KiB
121Elfogadva1ms316 KiB
122Elfogadva1ms508 KiB
123Elfogadva1ms508 KiB
124Elfogadva1ms500 KiB
125Elfogadva1ms316 KiB
126Elfogadva1ms500 KiB
127Elfogadva1ms400 KiB
128Elfogadva1ms316 KiB
129Elfogadva1ms500 KiB
130Elfogadva1ms508 KiB
131Elfogadva1ms316 KiB
132Időlimit túllépés1.072s1012 KiB
133Elfogadva2ms316 KiB
134Időlimit túllépés1.074s1324 KiB
135Időlimit túllépés1.074s820 KiB
136Időlimit túllépés1.1s808 KiB
137Időlimit túllépés1.092s756 KiB
138Időlimit túllépés1.092s724 KiB
139Elfogadva3ms356 KiB
140Időlimit túllépés1.1s6280 KiB
141Elfogadva697ms15412 KiB
142Időlimit túllépés1.08s15564 KiB
143Időlimit túllépés1.087s57876 KiB
144Időlimit túllépés1.085s48140 KiB
145Időlimit túllépés1.11s166396 KiB
146Időlimit túllépés1.088s83576 KiB
147Futási hiba546ms262144 KiB
148Időlimit túllépés1.092s179308 KiB
149Futási hiba379ms262144 KiB