156302025-02-21 11:49:59linhnkFertőzési sorozat (50 pont)cpp17Hibás válasz 48/5014ms604 KiB
#include <iostream>
#include <bits/stdc++.h>
#include<queue>

using namespace std;

int main()
{
    int n, m, k, a, b;
    cin>>n>>m>>k;
    vector<int> hal(k);
    vector<vector<int>> cs(n+1);
    vector<int> erdos(n+1, -1);
    vector<bool> alap(n+1, false);
    vector<bool> been(n+1, false);
    queue<int> q;
    vector<int> d;
    bool jaj=true;
    for(int i=0; i<k; i++){
        cin>>hal[i];
        alap[hal[i]]=true;
    }
    alap[hal[0]]=false;
    for(int i=0; i<m; i++){
        cin>>a>>b;
        cs[a].push_back(b);
        cs[b].push_back(a);
    }
    for(int h=1; h<n+1; h++){
            if(alap[h])
                continue;
            jaj=true;
            erdos.assign(n+1, -1);
            been.assign(n+1, false);
            //cout<<h<<endl;
            erdos[h]=0;
            q.push(h);
            /*been[h]=true;
            for(auto x:cs[h]){
                q.push(x);
                erdos[x]=1;
                //cout<<x<<"";
            }*/
            //cout<<endl;
            while(q.size()>0){
                if(!been[q.front()]){
                        been[q.front()]=true;
                    for(auto x:cs[q.front()]){
                        if(erdos[x]==-1){
                            erdos[x]=erdos[q.front()]+1;
                            q.push(x);
                            //cout<<q.front()<<" "<<x<<endl;
                        }
                    }
                }
                q.pop();
            }
            for(int i=0; i<k-1; i++){
                if(erdos[hal[i]]!=erdos[hal[i+1]]&&erdos[hal[i]]+1!=erdos[hal[i+1]]){
                    jaj=false;
                    break;
                }
            }

            if(!jaj){
                    continue;
                }
            for(auto x:erdos){
                    if(x!=-1){
                if(!alap[x]&&x<erdos[hal.back()]&&x>erdos[hal[0]]){
                    jaj=false;
                    break;

                }
                }
            }
            if(jaj){
                d.push_back(h);
            }
    }
    cout<<d.size()<<endl;
    for(auto x:d){
        cout<<x<<" ";
    }
    /*cout<<endl<<erdos.size()<<endl;
    for(auto x:erdos){
        cout<<x<<" ";
    }*/

}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base48/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/01ms316 KiB
3Elfogadva0/04ms508 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/22ms508 KiB
6Elfogadva2/24ms508 KiB
7Elfogadva2/24ms508 KiB
8Elfogadva2/24ms416 KiB
9Elfogadva2/24ms424 KiB
10Elfogadva2/214ms556 KiB
11Elfogadva1/12ms328 KiB
12Elfogadva2/28ms316 KiB
13Elfogadva2/28ms316 KiB
14Elfogadva2/27ms348 KiB
15Elfogadva2/27ms316 KiB
16Elfogadva2/27ms436 KiB
17Elfogadva2/24ms428 KiB
18Hibás válasz0/14ms316 KiB
19Elfogadva1/16ms316 KiB
20Elfogadva1/16ms432 KiB
21Elfogadva1/110ms432 KiB
22Elfogadva1/110ms436 KiB
23Hibás válasz0/18ms316 KiB
24Elfogadva1/18ms500 KiB
25Elfogadva1/18ms436 KiB
26Elfogadva1/19ms500 KiB
27Elfogadva1/112ms440 KiB
28Elfogadva1/19ms316 KiB
29Elfogadva1/110ms508 KiB
30Elfogadva1/19ms436 KiB
31Elfogadva1/19ms604 KiB
32Elfogadva1/19ms436 KiB
33Elfogadva1/12ms316 KiB
34Elfogadva1/112ms508 KiB
35Elfogadva1/113ms436 KiB
36Elfogadva1/112ms508 KiB
37Elfogadva1/112ms508 KiB
38Elfogadva1/112ms508 KiB
39Elfogadva1/19ms500 KiB
40Elfogadva1/17ms424 KiB