168542025-05-14 08:59:25AblablablaPletykacpp17Wrong answer 44/100186ms9012 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()
{
    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
base44/100
1Wrong answer0/01ms508 KiB
2Wrong answer0/029ms2356 KiB
3Partially correct1/21ms316 KiB
4Partially correct1/22ms316 KiB
5Partially correct1/22ms316 KiB
6Partially correct1/24ms564 KiB
7Partially correct2/44ms564 KiB
8Partially correct2/48ms912 KiB
9Partially correct2/48ms968 KiB
10Partially correct2/48ms1076 KiB
11Partially correct2/428ms2416 KiB
12Partially correct2/428ms2680 KiB
13Partially correct2/450ms3948 KiB
14Partially correct2/450ms3912 KiB
15Partially correct3/670ms5172 KiB
16Partially correct3/670ms5428 KiB
17Partially correct3/6101ms6756 KiB
18Partially correct3/698ms6660 KiB
19Partially correct3/6107ms7988 KiB
20Partially correct3/6108ms8244 KiB
21Partially correct3/6119ms7988 KiB
22Partially correct3/6116ms7476 KiB
23Time limit exceeded0/6185ms8824 KiB
24Time limit exceeded0/6186ms9012 KiB