Topla voda

Pitanja i problemi
1

Pitanje ili opis problema

Topla voda, zadatak C sa kvalifikacija II

Link ka zadatku ili odgovarajućoj stranici

https://arena.petlja.org/sr-Latn-rs/Competitions/Competition/171#tab_128915

Postovani, da li bi neko imao vremena i volje da pogleda moj kod jer stvarno ne znam gde je glich

    #include<iostream>
    #include<vector>

    using namespace std;

    vector<int> pipes[300001];
    int previous[300001];
    bool flag[300004];

    int trace_back(int a)
    {
         int c=0;
         while(!flag[a])
         {
                        flag[a]=true;
                        a=previous[a];
                        c++;
         }
         return c;
    }

    int main()
    {
        ios::sync_with_stdio(false);
        int n, m, x, y;
        cin>>n;
        for(int i=0; i<n-1; i++)
        {
                cin>>x>>y;
                pipes[x].push_back(y);
                pipes[y].push_back(x);
                previous[i]=0;
                flag[i]=false;
        }
        for(int i=1; i<=n; i++)
        {
                for(vector<int>::iterator s=pipes[i].begin(); s!=pipes[i].end(); s++)
                {
                                 if(!previous[*s])
                                 {
                                                 previous[*s]=i;
                                 }
                }
        }
        flag[1]=true;
        previous[1]=0;
        cin>>m;
        for(int i=1; i<=m; i++)
        {
                cin>>x;
                cout<<trace_back(x)<<"\n";
        }
        
        return 0;
    }

ubaceni su vector i iostream nego se ne prikazuje iz nekog razloga

2 
for(int i=1; i<=n; i++)
{
        for(vector<int>::iterator s=pipes[i].begin(); s!=pipes[i].end(); s++)
        {
                         if(!previous[*s])
                         {
                                         previous[*s]=i;
                         }
        }
}

Ovde ti je bug, ne mozes ovako da odredis ko je roditelj cvora

3

Hvala, a da li se iz inputa zna ko je parent, trenutno je arena under constuction pa ne vidim zadatak?
Tj. da li tipa 4 3 znaci da je 4 sigurno roditelj 3? Ako ne moze pojasnjenje za obradu porodicnog stabla

4

Ne znaci, onaj cvor koji vidis na putu od 1 ranije je parent onim cvorovima koje vidis za 1 korak kasnije.

primer 2.
4
1 4
4 3
2 4 … a 4 je parent 2

%20primer

Mozes da pogledas ovu stranicu za objasnjenje kako da nadjes parent svakom cvoru:

5

Hvala, samo imam sad nedoumicu. Znam sta je BFS nije to problem, ali ne vidim koliko se on razlikuje od moje metode (znam kako bfs ide, a sigurni smo da ako je 2 npr. ispred 3 sigurno je 2 parent od 3jke, ne vezano da li smo stigli do njega jos ili ne), s toga ne razumem kako da poboljsam resenje

6

1519998679257719226091
15199986792577192260912443×3258 2.1 MB

Ovo ti radi kod?

1 Like
7

Au, kakav previd, hvala puno