258302026-03-04 21:16:21csdavidCsillagok bábeli tornyacpp17Hibás válasz 0/1001.111s262144 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(){
    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);
        }
    }
    for (int i = 1; i <= n; i++){
        if (!a[i].scc){
            sccSize = 0;
            sccCount++;
            dfs2(i);
            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álasz8ms11316 KiB
2Időlimit túllépés1.093s205752 KiB
subtask20/10
3Elfogadva13ms11316 KiB
4Elfogadva9ms11316 KiB
5Elfogadva10ms11320 KiB
6Hibás válasz13ms11316 KiB
7Elfogadva12ms11316 KiB
8Elfogadva9ms11500 KiB
9Hibás válasz12ms11500 KiB
10Hibás válasz9ms11316 KiB
11Hibás válasz12ms11316 KiB
12Elfogadva10ms11560 KiB
subtask30/15
13Elfogadva12ms11316 KiB
14Elfogadva12ms11316 KiB
15Elfogadva9ms11336 KiB
16Elfogadva9ms11500 KiB
17Elfogadva112ms17200 KiB
18Időlimit túllépés1.105s103476 KiB
19Időlimit túllépés1.111s181196 KiB
20Időlimit túllépés1.11s186800 KiB
21Időlimit túllépés1.095s106068 KiB
22Időlimit túllépés1.088s78772 KiB
23Időlimit túllépés1.105s74548 KiB
24Időlimit túllépés1.105s102964 KiB
25Elfogadva146ms20788 KiB
subtask40/10
26Elfogadva13ms11316 KiB
27Elfogadva10ms11316 KiB
28Elfogadva13ms11316 KiB
29Elfogadva10ms11252 KiB
30Elfogadva9ms11320 KiB
31Hibás válasz9ms11300 KiB
32Hibás válasz105ms17720 KiB
33Hibás válasz317ms26688 KiB
34Elfogadva224ms25908 KiB
35Elfogadva324ms29236 KiB
subtask50/25
36Elfogadva13ms11316 KiB
37Elfogadva9ms11316 KiB
38Elfogadva10ms11320 KiB
39Hibás válasz13ms11316 KiB
40Elfogadva12ms11316 KiB
41Elfogadva9ms11500 KiB
42Hibás válasz12ms11500 KiB
43Hibás válasz9ms11316 KiB
44Hibás válasz12ms11316 KiB
45Elfogadva10ms11560 KiB
46Hibás válasz9ms11336 KiB
47Elfogadva13ms11572 KiB
48Elfogadva43ms13108 KiB
49Hibás válasz59ms13892 KiB
50Hibás válasz27ms17280 KiB
51Elfogadva17ms15412 KiB
52Elfogadva14ms13288 KiB
53Elfogadva13ms12340 KiB
54Hibás válasz13ms11520 KiB
55Elfogadva10ms11316 KiB
56Hibás válasz12ms11384 KiB
57Hibás válasz19ms12004 KiB
58Hibás válasz17ms11828 KiB
59Hibás válasz63ms14644 KiB
subtask60/40
60Hibás válasz9ms11316 KiB
61Időlimit túllépés1.098s177628 KiB
62Elfogadva13ms11316 KiB
63Elfogadva9ms11316 KiB
64Elfogadva10ms11320 KiB
65Hibás válasz13ms11316 KiB
66Elfogadva12ms11316 KiB
67Elfogadva9ms11500 KiB
68Hibás válasz12ms11500 KiB
69Hibás válasz9ms11316 KiB
70Hibás válasz12ms11316 KiB
71Elfogadva10ms11560 KiB
72Elfogadva12ms11316 KiB
73Elfogadva12ms11316 KiB
74Elfogadva9ms11336 KiB
75Elfogadva9ms11500 KiB
76Elfogadva112ms17200 KiB
77Időlimit túllépés1.105s103476 KiB
78Időlimit túllépés1.111s181196 KiB
79Időlimit túllépés1.11s186800 KiB
80Időlimit túllépés1.095s106068 KiB
81Időlimit túllépés1.088s78772 KiB
82Időlimit túllépés1.105s74548 KiB
83Időlimit túllépés1.105s102964 KiB
84Elfogadva146ms20788 KiB
85Elfogadva13ms11316 KiB
86Elfogadva10ms11316 KiB
87Elfogadva13ms11316 KiB
88Elfogadva10ms11252 KiB
89Elfogadva9ms11320 KiB
90Hibás válasz9ms11300 KiB
91Hibás válasz105ms17720 KiB
92Hibás válasz317ms26688 KiB
93Elfogadva224ms25908 KiB
94Elfogadva324ms29236 KiB
95Hibás válasz9ms11336 KiB
96Elfogadva13ms11572 KiB
97Elfogadva43ms13108 KiB
98Hibás válasz59ms13892 KiB
99Hibás válasz27ms17280 KiB
100Elfogadva17ms15412 KiB
101Elfogadva14ms13288 KiB
102Elfogadva13ms12340 KiB
103Hibás válasz13ms11520 KiB
104Elfogadva10ms11316 KiB
105Hibás válasz12ms11384 KiB
106Hibás válasz19ms12004 KiB
107Hibás válasz17ms11828 KiB
108Hibás válasz63ms14644 KiB
109Elfogadva64ms14892 KiB
110Időlimit túllépés1.093s120116 KiB
111Hibás válasz296ms26416 KiB
112Időlimit túllépés1.098s218616 KiB
113Időlimit túllépés1.095s245712 KiB
114Időlimit túllépés1.093s140800 KiB
115Időlimit túllépés1.106s130544 KiB
116Időlimit túllépés1.082s73264 KiB
117Időlimit túllépés1.093s75392 KiB
118Futási hiba691ms262144 KiB
119Futási hiba680ms262144 KiB
120Hibás válasz180ms18220 KiB
121Időlimit túllépés1.093s188420 KiB
122Időlimit túllépés1.095s233576 KiB
123Hibás válasz298ms24312 KiB
124Hibás válasz312ms25652 KiB
125Hibás válasz247ms22836 KiB