129572025-01-03 22:39:55BucsMateFertőzési sorozat (50 pont)cpp17Hibás válasz 47/5014ms508 KiB
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void megold(vector<vector<int>> &adj, vector<int> &megoldas, int fertozesi_sorozat[], int tavolsag[], int frekv_tavolsag[],
            int frekv_fertozott_tavolsag[], int K, int start)
{
    queue<int> q;
    q.push(start);
    tavolsag[start] = 1;
    frekv_tavolsag[1] = 1;
    int currNode, newNode;
    while(!q.empty()){
        currNode = q.front();
        q.pop();

        for(int i = 0; i < adj[currNode].size(); i++){
            newNode = adj[currNode][i];
            if(tavolsag[newNode] == 0){
                tavolsag[newNode] = tavolsag[currNode] + 1;
                frekv_tavolsag[tavolsag[newNode]]++;
                q.push(newNode);
            }
        }
    }

    frekv_fertozott_tavolsag[fertozesi_sorozat[0]]++;
    for(int i = 1; i < K; i++){
        frekv_fertozott_tavolsag[fertozesi_sorozat[i]]++;
        int d = tavolsag[fertozesi_sorozat[i]] - tavolsag[fertozesi_sorozat[i-1]];
        if(d != 0 && d != 1){
            return;
        }
    }

    int elso = tavolsag[fertozesi_sorozat[0]];
    int utolso = tavolsag[fertozesi_sorozat[K-1]];

    for(int i = elso + 1; i < utolso; i++){
        if(frekv_fertozott_tavolsag[i] != frekv_tavolsag[i]){
            return;
        }
    }
    megoldas.push_back(start);
}

int main()
{
    int N, M, K;
    cin >> N >> M >> K;
    int fertozesi_sorozat[501];
    for(int i = 0; i < K; i++){
        cin >> fertozesi_sorozat[i];
    }
    vector<vector<int>> adj(N+1, vector<int>());

    for(int i = 0; i < M; i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vector<int> megoldas;

    for(int start = 1; start <= N; start++){
        int tavolsag[501] = {}, frekv_tavolsag[501] = {}, frekv_fertozott_tavolsag[501] = {};
        megold(adj, megoldas, fertozesi_sorozat, tavolsag, frekv_tavolsag, frekv_fertozott_tavolsag, K, start);
    }
    cout << megoldas.size() << endl;
    for(int i = 0; i < megoldas.size(); i++){
        cout << megoldas[i] << " ";
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base47/50
1Elfogadva0/01ms320 KiB
2Elfogadva0/01ms500 KiB
3Elfogadva0/04ms320 KiB
4Elfogadva2/21ms320 KiB
5Elfogadva2/21ms320 KiB
6Elfogadva2/24ms320 KiB
7Elfogadva2/24ms424 KiB
8Elfogadva2/24ms320 KiB
9Elfogadva2/24ms320 KiB
10Elfogadva2/214ms444 KiB
11Elfogadva1/11ms320 KiB
12Elfogadva2/24ms508 KiB
13Elfogadva2/24ms436 KiB
14Elfogadva2/24ms444 KiB
15Elfogadva2/24ms320 KiB
16Elfogadva2/26ms436 KiB
17Elfogadva2/24ms500 KiB
18Hibás válasz0/14ms436 KiB
19Elfogadva1/14ms320 KiB
20Elfogadva1/14ms320 KiB
21Elfogadva1/114ms440 KiB
22Elfogadva1/113ms444 KiB
23Hibás válasz0/110ms320 KiB
24Elfogadva1/19ms440 KiB
25Elfogadva1/19ms440 KiB
26Elfogadva1/112ms320 KiB
27Elfogadva1/114ms444 KiB
28Elfogadva1/110ms508 KiB
29Elfogadva1/113ms440 KiB
30Elfogadva1/19ms448 KiB
31Elfogadva1/19ms352 KiB
32Elfogadva1/112ms448 KiB
33Hibás válasz0/114ms320 KiB
34Elfogadva1/114ms500 KiB
35Elfogadva1/114ms444 KiB
36Elfogadva1/114ms440 KiB
37Elfogadva1/114ms320 KiB
38Elfogadva1/114ms444 KiB
39Elfogadva1/112ms440 KiB
40Elfogadva1/114ms436 KiB