156812025-02-21 17:57:34999Fertőzési sorozat (50 pont)cpp17Hibás válasz 36/50354ms2596 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 1e12;

signed main(){
    int n,m,k;cin>>n>>m>>k;
    vector<vector<int>> fw(n, vector<int>(n,INF));
    vector<int> v(k);
    vector<int> volt(n);
    for(int &i:v){cin>>i;i--;volt[i]=1;}
    for(int i = 0;i<m;i++){
        int a,b;cin>>a>>b;
        fw[--a][--b]=1;
        fw[b][a]=1;
    }
    for(int i = 0;i<n;i++)fw[i][i]=0;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            for(int k = 0;k<n;k++){
                fw[k][j]=min(fw[k][j],fw[i][k]+fw[i][j]);
            }
        }
    }//for(int i = 0;i<n;i++){for(int j = 0;j<n;j++)cerr<<fw[i][j]<<' ';cerr<<endl;}
    vector<int> ans;
    for(int i = 0;i<n;i++){
        bool boo=true;
        if(volt[i])continue;
        for(int j=0;j<k;j++){
            int l=v[j];
            if(j==0)continue;
            if(!(fw[i][l]-fw[i][v[j-1]]<=1&&fw[i][l]-fw[i][v[j-1]]>=0)){
                boo=false;
                break;
            }
        }
        if(boo){
            ans.push_back(i);
        }
    }
    cout<<ans.size()<<endl;
    for(int i:ans)cout<<i+1<<' ';
    cout<<endl;
}
 
RészfeladatÖsszpontTesztVerdiktIdőMemória
base36/50
1Elfogadva0/01ms500 KiB
2Elfogadva0/01ms316 KiB
3Elfogadva0/030ms820 KiB
4Hibás válasz0/21ms316 KiB
5Elfogadva2/23ms356 KiB
6Elfogadva2/230ms904 KiB
7Elfogadva2/230ms896 KiB
8Elfogadva2/229ms892 KiB
9Hibás válasz0/230ms900 KiB
10Elfogadva2/2352ms2384 KiB
11Hibás válasz0/11ms316 KiB
12Elfogadva2/2349ms2376 KiB
13Elfogadva2/2349ms2380 KiB
14Elfogadva2/2349ms2204 KiB
15Elfogadva2/2354ms2356 KiB
16Elfogadva2/2351ms2384 KiB
17Elfogadva2/2351ms2384 KiB
18Elfogadva1/1354ms2376 KiB
19Elfogadva1/1349ms2384 KiB
20Elfogadva1/1349ms2384 KiB
21Elfogadva1/1354ms2280 KiB
22Elfogadva1/1349ms2356 KiB
23Elfogadva1/1354ms2384 KiB
24Hibás válasz0/1354ms2388 KiB
25Elfogadva1/1349ms2356 KiB
26Elfogadva1/1349ms2380 KiB
27Hibás válasz0/1351ms2376 KiB
28Hibás válasz0/1351ms2380 KiB
29Elfogadva1/1354ms2548 KiB
30Hibás válasz0/1354ms2392 KiB
31Hibás válasz0/1352ms2356 KiB
32Elfogadva1/1349ms2596 KiB
33Hibás válasz0/1349ms2548 KiB
34Hibás válasz0/1349ms2380 KiB
35Hibás válasz0/1349ms2384 KiB
36Hibás válasz0/1352ms2540 KiB
37Elfogadva1/1349ms2360 KiB
38Elfogadva1/1354ms2356 KiB
39Elfogadva1/1349ms2384 KiB
40Elfogadva1/1349ms2384 KiB