134862025-01-08 08:34:24Vkrisztian01Fertőzési sorozat (50 pont)cpp17Hibás válasz 2/5017ms2548 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)) ;
    vector<vector<int> > cnt(n + 1 , vector<int>(n + 1 , 0)) ;
    for(int i = 1 ; i <= n ; i ++)
    {
        d[i][i] = 0 ;
        cnt[i][0] = 1 ;
    }


    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 ;
                cnt[i][d[i][v] + 1 ]++ ;
                q.push(to) ;
            }
        }
    }

    vector<int> ans ;
    for(int i = 1 ; i <= n ; i++)
    {

        int d0 = d[i][v[0] ] ;
        bool good = true ;
        for(int j = 1 ; j < k ; j++)
        {
            int d1 = d[i][v[j - 1] ] ;
            int d2 = d[i][v[j] ] ;

            cnt[i][d1]-- ;

            if(d2 < d1 || (d2 - 1 != d0 && cnt[i][d2 - 1] > 0))
                good = false ;
        }

        if(good)
            ans.push_back(i) ;
    }

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


    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base2/50
1Hibás válasz0/01ms500 KiB
2Hibás válasz0/01ms316 KiB
3Hibás válasz0/04ms820 KiB
4Hibás válasz0/21ms316 KiB
5Hibás válasz0/21ms316 KiB
6Hibás válasz0/24ms928 KiB
7Hibás válasz0/24ms928 KiB
8Hibás válasz0/24ms772 KiB
9Hibás válasz0/24ms820 KiB
10Hibás válasz0/214ms2428 KiB
11Hibás válasz0/12ms412 KiB
12Hibás válasz0/26ms2428 KiB
13Hibás válasz0/27ms2428 KiB
14Hibás válasz0/26ms2548 KiB
15Hibás válasz0/26ms2356 KiB
16Hibás válasz0/27ms2356 KiB
17Hibás válasz0/26ms2212 KiB
18Hibás válasz0/17ms2356 KiB
19Hibás válasz0/17ms2356 KiB
20Hibás válasz0/14ms2184 KiB
21Hibás válasz0/114ms2440 KiB
22Hibás válasz0/114ms2436 KiB
23Hibás válasz0/112ms2436 KiB
24Hibás válasz0/112ms2356 KiB
25Hibás válasz0/19ms2436 KiB
26Hibás válasz0/113ms2440 KiB
27Hibás válasz0/114ms2432 KiB
28Hibás válasz0/110ms2432 KiB
29Hibás válasz0/113ms2436 KiB
30Hibás válasz0/110ms2356 KiB
31Hibás válasz0/110ms2356 KiB
32Hibás válasz0/112ms2436 KiB
33Elfogadva1/117ms2356 KiB
34Hibás válasz0/114ms2428 KiB
35Hibás válasz0/114ms2432 KiB
36Hibás válasz0/114ms2356 KiB
37Hibás válasz0/114ms2432 KiB
38Hibás válasz0/114ms2404 KiB
39Elfogadva1/113ms2432 KiB
40Hibás válasz0/114ms2432 KiB