258312026-03-04 21:20:33csdavidCsillagok bábeli tornyacpp17Hibás válasz 0/1001.103s262144 KiB
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int n, m;

struct Szereplo{
    int beszel; // milyen nyelvet beszél az adott szereplő
    vector<int> megert; // milyen nyelveket ert meg az adott szereplő
    int scc = 0;
    bool bejart = false;
    vector<int> adj; // szomszedsagi lista
    vector<int> radj; // forditott szomszedsagi lista
};

Szereplo a[100001];
vector<int> nyelv[100001]; // a nyelv[i] vektorban taroljuk a az i nyelvet beszelo szereploket
stack<int> s;
int sccCount = 0; // Osszefuggo komponensek szama
int sccSize = 0; // Jelenlegi osszefuggo komponens merete
int maxi = 0; // Legnagyobb osszefuggo komponens merete
int biggestscc; // Legnagyobb osszefuggo komponens azonositoja

void dfs1(int x){
    a[x].bejart = 1;
    for (auto& it : a[x].adj){
        if (!a[it].bejart){
            dfs1(it);
        }
    }
    s.push(x);
}

void dfs2(int x){
    a[x].scc = sccCount;
    for (auto& it : a[x].adj){
        if (!a[it].scc){
            dfs2(it);
        }
    }
    sccSize++;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> a[i].beszel;
        nyelv[a[i].beszel].push_back(i);
    }

    for (int i = 1; i <= n; i++){
        int k;
        cin >> k;
        a[i].megert.resize(k);
        for (int j = 0; j < k; j++){
            cin >> a[i].megert[j];
            for (auto& it : nyelv[a[i].megert[j]]){
                a[i].adj.push_back(it);
                a[it].radj.push_back(i);
            }
        }
        for (auto& it : nyelv[a[i].beszel]){
            a[i].adj.push_back(it);
            a[it].radj.push_back(i);
        }
    }

    for (int i = 1; i <= n; i++){
        if (!a[i].bejart){
            dfs1(i);
        }
    }
    while (!s.empty()){
        int x = s.top();
        s.pop();
        if (!a[x].scc){
            sccSize = 0;
            sccCount++;
            dfs2(x);
            if (sccSize > maxi){
                maxi = sccSize;
                biggestscc = sccCount;
            }
        }
    }
    cout << maxi << '\n';
    for (int i = 1; i <= n; i++){
        if (a[i].scc == biggestscc) cout << i << ' ';
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Hibás válasz10ms11316 KiB
2Időlimit túllépés1.047s262144 KiB
subtask20/10
3Elfogadva12ms11508 KiB
4Elfogadva12ms11316 KiB
5Elfogadva9ms11512 KiB
6Hibás válasz9ms11360 KiB
7Elfogadva9ms11512 KiB
8Elfogadva9ms11316 KiB
9Hibás válasz12ms11332 KiB
10Hibás válasz12ms11512 KiB
11Hibás válasz13ms11316 KiB
12Hibás válasz9ms11320 KiB
subtask30/15
13Elfogadva12ms11316 KiB
14Elfogadva9ms11316 KiB
15Elfogadva12ms11316 KiB
16Elfogadva9ms11316 KiB
17Elfogadva125ms16948 KiB
18Időlimit túllépés1.088s107112 KiB
19Időlimit túllépés1.092s204816 KiB
20Időlimit túllépés1.093s182832 KiB
21Időlimit túllépés1.092s96508 KiB
22Időlimit túllépés1.095s78640 KiB
23Időlimit túllépés1.098s89400 KiB
24Időlimit túllépés1.098s101912 KiB
25Elfogadva125ms20020 KiB
subtask40/10
26Elfogadva12ms11508 KiB
27Elfogadva12ms11316 KiB
28Elfogadva9ms11564 KiB
29Elfogadva9ms11512 KiB
30Elfogadva9ms11316 KiB
31Hibás válasz12ms11316 KiB
32Hibás válasz74ms17564 KiB
33Hibás válasz239ms25676 KiB
34Elfogadva224ms24660 KiB
35Elfogadva181ms27956 KiB
subtask50/25
36Elfogadva12ms11508 KiB
37Elfogadva12ms11316 KiB
38Elfogadva9ms11512 KiB
39Hibás válasz9ms11360 KiB
40Elfogadva9ms11512 KiB
41Elfogadva9ms11316 KiB
42Hibás válasz12ms11332 KiB
43Hibás válasz12ms11512 KiB
44Hibás válasz13ms11316 KiB
45Hibás válasz9ms11320 KiB
46Hibás válasz9ms11500 KiB
47Elfogadva14ms11316 KiB
48Elfogadva26ms12852 KiB
49Hibás válasz29ms13360 KiB
50Hibás válasz28ms17460 KiB
51Elfogadva17ms15492 KiB
52Elfogadva17ms13364 KiB
53Elfogadva12ms12248 KiB
54Hibás válasz13ms11320 KiB
55Elfogadva9ms11316 KiB
56Hibás válasz10ms11584 KiB
57Hibás válasz14ms11780 KiB
58Hibás válasz16ms11572 KiB
59Hibás válasz34ms14236 KiB
subtask60/40
60Hibás válasz9ms11508 KiB
61Időlimit túllépés1.09s172340 KiB
62Elfogadva12ms11508 KiB
63Elfogadva12ms11316 KiB
64Elfogadva9ms11512 KiB
65Hibás válasz9ms11360 KiB
66Elfogadva9ms11512 KiB
67Elfogadva9ms11316 KiB
68Hibás válasz12ms11332 KiB
69Hibás válasz12ms11512 KiB
70Hibás válasz13ms11316 KiB
71Hibás válasz9ms11320 KiB
72Elfogadva12ms11316 KiB
73Elfogadva9ms11316 KiB
74Elfogadva12ms11316 KiB
75Elfogadva9ms11316 KiB
76Elfogadva125ms16948 KiB
77Időlimit túllépés1.088s107112 KiB
78Időlimit túllépés1.092s204816 KiB
79Időlimit túllépés1.093s182832 KiB
80Időlimit túllépés1.092s96508 KiB
81Időlimit túllépés1.095s78640 KiB
82Időlimit túllépés1.098s89400 KiB
83Időlimit túllépés1.098s101912 KiB
84Elfogadva125ms20020 KiB
85Elfogadva12ms11508 KiB
86Elfogadva12ms11316 KiB
87Elfogadva9ms11564 KiB
88Elfogadva9ms11512 KiB
89Elfogadva9ms11316 KiB
90Hibás válasz12ms11316 KiB
91Hibás válasz74ms17564 KiB
92Hibás válasz239ms25676 KiB
93Elfogadva224ms24660 KiB
94Elfogadva181ms27956 KiB
95Hibás válasz9ms11500 KiB
96Elfogadva14ms11316 KiB
97Elfogadva26ms12852 KiB
98Hibás válasz29ms13360 KiB
99Hibás válasz28ms17460 KiB
100Elfogadva17ms15492 KiB
101Elfogadva17ms13364 KiB
102Elfogadva12ms12248 KiB
103Hibás válasz13ms11320 KiB
104Elfogadva9ms11316 KiB
105Hibás válasz10ms11584 KiB
106Hibás válasz14ms11780 KiB
107Hibás válasz16ms11572 KiB
108Hibás válasz34ms14236 KiB
109Elfogadva39ms14384 KiB
110Elfogadva846ms125492 KiB
111Hibás válasz233ms24884 KiB
112Időlimit túllépés1.098s142660 KiB
113Időlimit túllépés1.024s262144 KiB
114Időlimit túllépés1.1s183968 KiB
115Időlimit túllépés1.095s98088 KiB
116Időlimit túllépés1.082s59720 KiB
117Időlimit túllépés1.082s69192 KiB
118Futási hiba686ms262144 KiB
119Futási hiba578ms262144 KiB
120Hibás válasz135ms18228 KiB
121Időlimit túllépés1.1s178392 KiB
122Időlimit túllépés1.103s184780 KiB
123Hibás válasz171ms23156 KiB
124Hibás válasz238ms24228 KiB
125Hibás válasz179ms23076 KiB