168552025-05-14 09:00:27AblablablaPletykacpp17Wrong answer 50/100114ms10328 KiB
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> csucsok;
vector<bool> bejart, kezdo;
vector<int> allapot;

int dfs(int akt){
    bejart[akt] = 1;
    int vissza = 1;

    for(int x : csucsok[akt]){
        if(bejart[x]) continue;

        vissza += dfs(x);
    }

    return vissza;
}

int ps, pt;

bool szamol(int akt){
    bejart[akt] = 1;

    assert(allapot[akt] != 3);
    //assert(allapot[akt] == 1 || allapot[akt] == 2);

    if(allapot[akt] != 1 && allapot[akt] != 2){
        return 0;
    }

    bool vissza = kezdo[akt];

    if(allapot[akt] == 1){
        pt++;
    } else{
        ps++;
    }

    for(int x : csucsok[akt]){
        if(bejart[x]) continue;

        vissza |= szamol(x);
    }

    return vissza;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m, k;
    cin >> n >> m >> k;

    kezdo.assign(n, 0);
    vector<int> kezd(k);
    for(int &x : kezd){
        cin >> x;
        x--;

        kezdo[x] = 1;
    }

    csucsok.assign(n, vector<int>());
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;

        csucsok[a].push_back(b);
        csucsok[b].push_back(a);
    }

    int ans = 0;
    queue<int> bejar;
    bejart.assign(n, 0);
    allapot.assign(n, 0);

    for(int x : kezd){
        bejar.push(x);
        allapot[x] = 2;
    }

    while(!bejar.empty()){
        int akt = bejar.front();
        bejar.pop();

        if(bejart[akt]) continue;
        bejart[akt] = 1;

        int lesz = 3 - allapot[akt];

        for(int x : csucsok[akt]){
            if(allapot[x] != 3 && allapot[x] != lesz){
                allapot[x] += lesz;
            }

            if(bejart[x]) continue;

            bejar.push(x);
        }
    }

    bejart.assign(n, 0);

    for(int i = 0; i < n; i++){
        if(allapot[i] == 3 && !bejart[i]){
            int a = dfs(i);
            ans += a;
        }
    }

    int a = 0, b = 0;
    for(int i = 0; i < n; i++){
        if(!bejart[i]){
            ps = 0;
            pt = 0;

            if(szamol(i) && ps + pt != 1){
                a += ps;
                b += pt;
            }
        }
    }

    cout << max(ans + max(a, b), k) << "\n";
}
SubtaskSumTestVerdictTimeMemory
base50/100
1Wrong answer0/01ms316 KiB
2Wrong answer0/016ms2356 KiB
3Partially correct1/21ms316 KiB
4Partially correct1/21ms316 KiB
5Partially correct1/22ms316 KiB
6Partially correct1/23ms564 KiB
7Partially correct2/43ms564 KiB
8Partially correct2/44ms1076 KiB
9Partially correct2/44ms1076 KiB
10Partially correct2/46ms1028 KiB
11Partially correct2/417ms2464 KiB
12Partially correct2/417ms2960 KiB
13Partially correct2/427ms3896 KiB
14Partially correct2/427ms3912 KiB
15Partially correct3/643ms5168 KiB
16Partially correct3/639ms5428 KiB
17Partially correct3/664ms6780 KiB
18Partially correct3/652ms6764 KiB
19Partially correct3/676ms8032 KiB
20Partially correct3/659ms8276 KiB
21Partially correct3/659ms7988 KiB
22Partially correct3/665ms7468 KiB
23Partially correct3/6114ms10328 KiB
24Partially correct3/6104ms10292 KiB