200202025-12-31 08:42:12VargaVivienVárosnézéscpp17Wrong answer 20/8032ms2464 KiB
#include <iostream>
#include <vector>
#include <string>

using namespace std;


vector <vector<int>> terkep;
int varos_lista[20001];
vector<bool> visited(200001,false);
vector<int> reszeredmeny(200001,-100);
int szam[20001];
int n;
int dist =-1;
int hossz=0;
void latogatas(int varos, int *latvanyossag, int szint)
{
   // bool vege = false;
    //vector<int> maximum;
   // vector<int> temp;
    int maxi = -2;
   // int ch_v=0;
   // cout << "szam" << &szam << endl;
   // cout << "temp" << &temp << endl;
   visited[varos]=true;
    if(varos == n)
    {
     reszeredmeny[n]=latvanyossag[varos - 1];
     varos_lista[szint]=varos;
     szam[n]=szint;
     visited[varos]=false;
     return;
     }
     if (terkep[varos].size()==0)
     {
      reszeredmeny[varos]=-1;
      visited[varos]=false;
      return;
     }
      else{
            for(auto x : terkep[varos])
        {

        if( reszeredmeny[x]< -1&& !visited[x]){

        latogatas(x, latvanyossag,  szint+1);
           }

        if(reszeredmeny[x]>maxi && !visited[x])
        {

            maxi=reszeredmeny[x];
            if (maxi>=0){
            varos_lista[szint]=varos;
            reszeredmeny[varos]=maxi+latvanyossag[varos - 1];
            szam[varos]=szam[x];
            }
            else
            {
             maxi=-1;
             reszeredmeny[varos]=maxi;
            }
        }
        }
        visited[varos]=false;
        }

}

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


    terkep.resize(n+1);
    for(int i = 0; i < m; i++)
    {
        cin >> x >> y;
        terkep[x].push_back(y);

    }
    int db = 0;
latogatas(1, numbers, 0);
    if (reszeredmeny[1]>=0)
    {
        cout << reszeredmeny[1] << endl;
        //cout << szam.size()<< endl;
        for (int j=0;j<=szam[1]; j++)
        {
            cout << varos_lista[j] << " ";
        }
    }
    else
    {
        cout << -1 << endl;
    }
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted2ms1076 KiB
subtask220/20
2Accepted1ms1076 KiB
3Accepted2ms1076 KiB
4Accepted2ms1076 KiB
5Accepted6ms1332 KiB
6Accepted3ms1332 KiB
7Accepted8ms1588 KiB
8Accepted8ms1604 KiB
9Accepted1ms1076 KiB
10Accepted14ms2464 KiB
11Accepted2ms1076 KiB
12Accepted1ms1076 KiB
subtask30/25
13Wrong answer2ms1076 KiB
14Accepted2ms1076 KiB
15Accepted2ms1092 KiB
16Wrong answer2ms1076 KiB
17Accepted2ms1076 KiB
18Wrong answer2ms1128 KiB
19Accepted2ms1224 KiB
20Accepted2ms1076 KiB
21Accepted1ms1080 KiB
22Wrong answer4ms1076 KiB
23Accepted3ms1084 KiB
24Wrong answer4ms1264 KiB
25Wrong answer4ms1076 KiB
26Accepted4ms1076 KiB
27Accepted4ms1076 KiB
28Wrong answer25ms1476 KiB
29Wrong answer6ms1332 KiB
30Wrong answer27ms1588 KiB
31Accepted16ms1552 KiB
32Accepted32ms1736 KiB
33Accepted10ms1860 KiB
subtask40/20
34Accepted1ms1076 KiB
35Accepted2ms1076 KiB
36Accepted2ms1076 KiB
37Accepted2ms1260 KiB
38Wrong answer2ms1076 KiB
39Accepted2ms1212 KiB
40Accepted2ms1076 KiB
41Accepted2ms1164 KiB
42Accepted2ms1076 KiB
43Accepted2ms1076 KiB
44Wrong answer1ms1076 KiB
45Accepted2ms1076 KiB
46Wrong answer2ms1080 KiB
47Wrong answer2ms1076 KiB
48Accepted2ms1144 KiB
49Accepted2ms1076 KiB
50Accepted2ms1080 KiB
51Accepted2ms1080 KiB
52Accepted2ms1272 KiB
53Accepted2ms1076 KiB
54Accepted2ms1076 KiB
55Accepted2ms1288 KiB
56Wrong answer2ms1076 KiB
57Wrong answer2ms1076 KiB
58Wrong answer2ms1176 KiB
59Wrong answer2ms988 KiB
60Accepted2ms1080 KiB
61Accepted2ms1272 KiB
62Wrong answer2ms1080 KiB
63Wrong answer1ms1076 KiB
64Accepted2ms1332 KiB
65Accepted2ms1076 KiB
66Wrong answer2ms1076 KiB
subtask50/15
67Accepted1ms1076 KiB
68Accepted1ms1076 KiB
69Accepted2ms1076 KiB
70Accepted2ms1076 KiB
71Accepted6ms1332 KiB
72Accepted3ms1332 KiB
73Accepted8ms1588 KiB
74Accepted8ms1604 KiB
75Accepted1ms1076 KiB
76Accepted14ms2464 KiB
77Accepted2ms1076 KiB
78Accepted1ms1076 KiB
79Wrong answer2ms1076 KiB
80Accepted2ms1076 KiB
81Accepted2ms1092 KiB
82Wrong answer2ms1076 KiB
83Accepted2ms1076 KiB
84Wrong answer2ms1128 KiB
85Accepted2ms1224 KiB
86Accepted2ms1076 KiB
87Accepted1ms1080 KiB
88Wrong answer4ms1076 KiB
89Accepted3ms1084 KiB
90Wrong answer4ms1264 KiB
91Wrong answer4ms1076 KiB
92Accepted4ms1076 KiB
93Accepted4ms1076 KiB
94Wrong answer25ms1476 KiB
95Wrong answer6ms1332 KiB
96Wrong answer27ms1588 KiB
97Accepted16ms1552 KiB
98Accepted32ms1736 KiB
99Accepted10ms1860 KiB
100Accepted2ms1076 KiB
101Accepted2ms1076 KiB
102Accepted2ms1260 KiB
103Wrong answer2ms1076 KiB
104Accepted2ms1212 KiB
105Accepted2ms1076 KiB
106Accepted2ms1164 KiB
107Accepted2ms1076 KiB
108Accepted2ms1076 KiB
109Wrong answer1ms1076 KiB
110Accepted2ms1076 KiB
111Wrong answer2ms1080 KiB
112Wrong answer2ms1076 KiB
113Accepted2ms1144 KiB
114Accepted2ms1076 KiB
115Accepted2ms1080 KiB
116Accepted2ms1080 KiB
117Accepted2ms1272 KiB
118Accepted2ms1076 KiB
119Accepted2ms1076 KiB
120Accepted2ms1288 KiB
121Wrong answer2ms1076 KiB
122Wrong answer2ms1076 KiB
123Wrong answer2ms1176 KiB
124Wrong answer2ms988 KiB
125Accepted2ms1080 KiB
126Accepted2ms1272 KiB
127Wrong answer2ms1080 KiB
128Wrong answer1ms1076 KiB
129Accepted2ms1332 KiB
130Accepted2ms1076 KiB
131Wrong answer2ms1076 KiB
132Accepted4ms1076 KiB
133Accepted2ms1264 KiB
134Accepted4ms1076 KiB
135Accepted3ms1076 KiB
136Wrong answer3ms1240 KiB
137Accepted3ms1076 KiB
138Wrong answer4ms1076 KiB
139Accepted3ms1076 KiB
140Wrong answer6ms1456 KiB
141Wrong answer4ms1516 KiB
142Wrong answer9ms1588 KiB
143Wrong answer9ms1656 KiB
144Wrong answer12ms1844 KiB
145Wrong answer8ms1496 KiB
146Wrong answer20ms2340 KiB
147Wrong answer17ms2080 KiB
148Wrong answer16ms1812 KiB
149Wrong answer10ms1700 KiB