134232025-01-07 21:57:42Vkrisztian01Fertőzési sorozat (50 pont)cpp17Wrong answer 42/5014ms1516 KiB
#include <iostream>
#include<bits/stdc++.h>

using namespace std;
const int inf = 1e5 ;

int main()
{
    int n , m , k ;
    cin >> n >> m >> k ;

    vector<int> v(k) ;
    for(int i = 0 ; i < k ; i++)
        cin >> v[i] ;

    vector<vector<int> > adj(n + 1) ;
    for(int i = 1 ; i <= m ; i++)
    {
        int u , v ;
        cin >> u >> v ;

        adj[u].push_back(v) ;
        adj[v].push_back(u) ;
    }

    vector<vector<int> > d(n + 1 , vector<int>(n + 1 , inf)) ;
    for(int i = 1 ; i <= n ; i ++)
        d[i][i] = 0 ;

    for(int i = 1 ; i <= n ; i++)
    {
        queue<int> q ;
        q.push(i) ;
        while(!q.empty())
        {
            int v = q.front() ;
            q.pop() ;

            for(int to : adj[v])
            {
                if(d[i][to] != inf) continue ;
                d[i][to] = d[i][v] + 1 ;
                q.push(to) ;
            }
        }
    }

    vector<int> ans ;
    for(int i = 1 ; i <= n ; i++)
    {
        bool good = true ;
        for(int j = 1 ; j < k ; j++)
            if(d[i][v[j] ] < d[i][v[j - 1] ] || d[i][v[j] ] > d[i][v[j - 1] ] + 1)
                good = false ;
        if(good)
            ans.push_back(i) ;
    }

    cout << ans.size() << "\n" ;
    for(int v : ans)
        cout << v << " " ;


    return 0;
}
SubtaskSumTestVerdictTimeMemory
base42/50
1Accepted0/01ms316 KiB
2Accepted0/01ms316 KiB
3Accepted0/04ms564 KiB
4Accepted2/21ms316 KiB
5Accepted2/21ms412 KiB
6Accepted2/24ms748 KiB
7Accepted2/24ms564 KiB
8Accepted2/24ms564 KiB
9Accepted2/24ms564 KiB
10Accepted2/213ms1440 KiB
11Accepted1/12ms316 KiB
12Accepted2/24ms1332 KiB
13Accepted2/26ms1432 KiB
14Accepted2/24ms1516 KiB
15Accepted2/24ms1332 KiB
16Accepted2/26ms1332 KiB
17Accepted2/24ms1412 KiB
18Accepted1/14ms1364 KiB
19Accepted1/16ms1332 KiB
20Accepted1/14ms1332 KiB
21Accepted1/113ms1332 KiB
22Accepted1/112ms1440 KiB
23Accepted1/19ms1332 KiB
24Wrong answer0/19ms1332 KiB
25Accepted1/18ms1332 KiB
26Accepted1/110ms1444 KiB
27Wrong answer0/113ms1440 KiB
28Wrong answer0/110ms1332 KiB
29Accepted1/112ms1444 KiB
30Wrong answer0/19ms1332 KiB
31Wrong answer0/19ms1332 KiB
32Accepted1/110ms1444 KiB
33Accepted1/114ms1336 KiB
34Wrong answer0/113ms1332 KiB
35Wrong answer0/113ms1440 KiB
36Wrong answer0/112ms1332 KiB
37Accepted1/113ms1332 KiB
38Accepted1/113ms1408 KiB
39Accepted1/110ms1436 KiB
40Accepted1/113ms1444 KiB