150872025-02-12 16:58:21iSamu7598Fertőzési sorozat (50 pont)cpp17Hibás válasz 4/5014ms548 KiB
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,m,k; cin>>n>>m>>k;
    vector<int> v(k+1);
    for(int i=1; i<=k; i++)
        cin>>v[i];
    vector<vector<int> > adj(n+1);
    for(int i=0; i<m; i++)
    {
        int a,b; cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vector<bool> bent(n+1);
    for(int i=1; i<=k; i++){
        bent[i]=1;
    }
    vector<int> ans;
    for(int kezd=1; kezd<=n; kezd++)
    {
        queue<int> q;
        vector<int> dist(n+1, n+1);
        q.push(kezd);
        dist[kezd]=0;
        while(!q.empty())
        {
            int cs=q.front();
            q.pop();
            for(int j=0; j<adj[cs].size(); j++){
                   int i=adj[cs][j];
                if(dist[cs]+1<dist[i])
            {
                dist[i]=dist[cs]+1;
                q.push(i);
            }
            }
        }
                /*for(int i=1; i<=n; i++){
            cout<<dist[i]<<" ";
        }
        cout<<endl;*/
        bool jo=1;
        for(int i=2; i<=k; i++)
            if(dist[v[i-1]]>dist[v[i]]) jo=0;
        if(!jo) continue;
        int elso=n+1,utso=0;
        for(int i=1; i<=n; i++)
            if(bent[i])
        {
            elso=min(elso,dist[i]);
            utso=max(utso,dist[i]);
        }

        //kozotte mindennek benne kell lennie
        for(int i=1; i<=n; i++)
            if(dist[i]>elso && dist[i]<utso && !bent[i] || (bent[i] && (dist[i]<elso || dist[i]>utso))) jo=0;
        if(jo) ans.push_back(kezd);
    }
    cout<<ans.size()<<"\n";
    for(int j=0; j<ans.size(); j++){
        int i=ans[j];
        cout<<i<<" ";
    }
    cout<<"\n";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base4/50
1Hibás válasz0/01ms316 KiB
2Hibás válasz0/01ms316 KiB
3Hibás válasz0/04ms316 KiB
4Elfogadva2/21ms316 KiB
5Hibás válasz0/22ms412 KiB
6Hibás válasz0/24ms508 KiB
7Hibás válasz0/24ms316 KiB
8Hibás válasz0/24ms508 KiB
9Hibás válasz0/24ms412 KiB
10Hibás válasz0/214ms436 KiB
11Elfogadva1/11ms316 KiB
12Hibás válasz0/26ms316 KiB
13Hibás válasz0/27ms428 KiB
14Hibás válasz0/24ms316 KiB
15Hibás válasz0/26ms508 KiB
16Hibás válasz0/26ms548 KiB
17Hibás válasz0/24ms316 KiB
18Hibás válasz0/14ms500 KiB
19Hibás válasz0/14ms328 KiB
20Hibás válasz0/14ms316 KiB
21Hibás válasz0/112ms316 KiB
22Hibás válasz0/112ms432 KiB
23Hibás válasz0/19ms508 KiB
24Hibás válasz0/18ms436 KiB
25Hibás válasz0/18ms320 KiB
26Hibás válasz0/110ms316 KiB
27Hibás válasz0/112ms432 KiB
28Hibás válasz0/19ms432 KiB
29Hibás válasz0/112ms444 KiB
30Hibás válasz0/19ms368 KiB
31Hibás válasz0/19ms412 KiB
32Hibás válasz0/110ms316 KiB
33Hibás válasz0/113ms500 KiB
34Hibás válasz0/113ms328 KiB
35Hibás válasz0/113ms436 KiB
36Hibás válasz0/112ms428 KiB
37Hibás válasz0/112ms432 KiB
38Hibás válasz0/112ms316 KiB
39Elfogadva1/110ms432 KiB
40Hibás válasz0/112ms436 KiB