152032025-02-16 15:22:06999Fertőzési sorozat (50 pont)cpp17Hibás válasz 42/50163ms1436 KiB
// Source: https://usaco.guide/general/io

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

int main() {
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, K;
    cin >> n >> m >> K;
    vector<vector<int> > d(n+1, vector<int>(n+1, 1000));
    vector<int> a(K);
    for(int i = 0; i < K; i++) {
        cin >> a[i];
    }
    for(int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        d[x][y] = d[y][x] = 1;
    }
 
    for(int i = 1; i <= n; i++) {
        d[i][i] = 0;
    }
 
    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
/*
    for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                cerr << d[i][j] << ' ';
            }cerr << endl;
        }
*/
    int elozo = 0;
    vector<long long> ansv;
    
    //cout << d[3][6] << endl;
    //cout << d[4][3] << endl;
    
    for(int i = 1; i <= n; i++) {
        elozo = 0;
        bool joe = 1;
        for(int J = 0; J < K; J++) {
            int j = a[J];
            if (J==0) {
                elozo = d[i][j];
            } else {
                if (d[i][j] - elozo <= 1 && d[i][j] - elozo >= 0) {
                    elozo = d[i][j];
                } else {
                    joe = 0;
                }
            }
        }
        if (joe) {
            ansv.push_back(i);
        }
    }
    cout<<ansv.size()<<endl;
    for(int x : ansv) {
        cout << x << ' ';
    }
}
 
RészfeladatÖsszpontTesztVerdiktIdőMemória
base42/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/01ms316 KiB
3Elfogadva0/021ms680 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/22ms316 KiB
6Elfogadva2/221ms676 KiB
7Elfogadva2/221ms672 KiB
8Elfogadva2/221ms748 KiB
9Elfogadva2/221ms676 KiB
10Elfogadva2/2162ms1424 KiB
11Elfogadva1/11ms316 KiB
12Elfogadva2/2162ms1332 KiB
13Elfogadva2/2162ms1424 KiB
14Elfogadva2/2162ms1424 KiB
15Elfogadva2/2162ms1332 KiB
16Elfogadva2/2162ms1424 KiB
17Elfogadva2/2162ms1432 KiB
18Elfogadva1/1162ms1332 KiB
19Elfogadva1/1162ms1416 KiB
20Elfogadva1/1162ms1424 KiB
21Elfogadva1/1162ms1428 KiB
22Elfogadva1/1162ms1424 KiB
23Elfogadva1/1162ms1332 KiB
24Hibás válasz0/1162ms1332 KiB
25Elfogadva1/1162ms1420 KiB
26Elfogadva1/1162ms1428 KiB
27Hibás válasz0/1162ms1332 KiB
28Hibás válasz0/1162ms1428 KiB
29Elfogadva1/1162ms1332 KiB
30Hibás válasz0/1162ms1424 KiB
31Hibás válasz0/1163ms1416 KiB
32Elfogadva1/1162ms1332 KiB
33Elfogadva1/1163ms1332 KiB
34Hibás válasz0/1162ms1332 KiB
35Hibás válasz0/1163ms1332 KiB
36Hibás válasz0/1162ms1436 KiB
37Elfogadva1/1162ms1332 KiB
38Elfogadva1/1163ms1332 KiB
39Elfogadva1/1162ms1332 KiB
40Elfogadva1/1163ms1332 KiB