258312026-03-04 21:20:33csdavidCsillagok bábeli tornyacpp17Wrong answer 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 << ' ';
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Wrong answer10ms11316 KiB
2Time limit exceeded1.047s262144 KiB
subtask20/10
3Accepted12ms11508 KiB
4Accepted12ms11316 KiB
5Accepted9ms11512 KiB
6Wrong answer9ms11360 KiB
7Accepted9ms11512 KiB
8Accepted9ms11316 KiB
9Wrong answer12ms11332 KiB
10Wrong answer12ms11512 KiB
11Wrong answer13ms11316 KiB
12Wrong answer9ms11320 KiB
subtask30/15
13Accepted12ms11316 KiB
14Accepted9ms11316 KiB
15Accepted12ms11316 KiB
16Accepted9ms11316 KiB
17Accepted125ms16948 KiB
18Time limit exceeded1.088s107112 KiB
19Time limit exceeded1.092s204816 KiB
20Time limit exceeded1.093s182832 KiB
21Time limit exceeded1.092s96508 KiB
22Time limit exceeded1.095s78640 KiB
23Time limit exceeded1.098s89400 KiB
24Time limit exceeded1.098s101912 KiB
25Accepted125ms20020 KiB
subtask40/10
26Accepted12ms11508 KiB
27Accepted12ms11316 KiB
28Accepted9ms11564 KiB
29Accepted9ms11512 KiB
30Accepted9ms11316 KiB
31Wrong answer12ms11316 KiB
32Wrong answer74ms17564 KiB
33Wrong answer239ms25676 KiB
34Accepted224ms24660 KiB
35Accepted181ms27956 KiB
subtask50/25
36Accepted12ms11508 KiB
37Accepted12ms11316 KiB
38Accepted9ms11512 KiB
39Wrong answer9ms11360 KiB
40Accepted9ms11512 KiB
41Accepted9ms11316 KiB
42Wrong answer12ms11332 KiB
43Wrong answer12ms11512 KiB
44Wrong answer13ms11316 KiB
45Wrong answer9ms11320 KiB
46Wrong answer9ms11500 KiB
47Accepted14ms11316 KiB
48Accepted26ms12852 KiB
49Wrong answer29ms13360 KiB
50Wrong answer28ms17460 KiB
51Accepted17ms15492 KiB
52Accepted17ms13364 KiB
53Accepted12ms12248 KiB
54Wrong answer13ms11320 KiB
55Accepted9ms11316 KiB
56Wrong answer10ms11584 KiB
57Wrong answer14ms11780 KiB
58Wrong answer16ms11572 KiB
59Wrong answer34ms14236 KiB
subtask60/40
60Wrong answer9ms11508 KiB
61Time limit exceeded1.09s172340 KiB
62Accepted12ms11508 KiB
63Accepted12ms11316 KiB
64Accepted9ms11512 KiB
65Wrong answer9ms11360 KiB
66Accepted9ms11512 KiB
67Accepted9ms11316 KiB
68Wrong answer12ms11332 KiB
69Wrong answer12ms11512 KiB
70Wrong answer13ms11316 KiB
71Wrong answer9ms11320 KiB
72Accepted12ms11316 KiB
73Accepted9ms11316 KiB
74Accepted12ms11316 KiB
75Accepted9ms11316 KiB
76Accepted125ms16948 KiB
77Time limit exceeded1.088s107112 KiB
78Time limit exceeded1.092s204816 KiB
79Time limit exceeded1.093s182832 KiB
80Time limit exceeded1.092s96508 KiB
81Time limit exceeded1.095s78640 KiB
82Time limit exceeded1.098s89400 KiB
83Time limit exceeded1.098s101912 KiB
84Accepted125ms20020 KiB
85Accepted12ms11508 KiB
86Accepted12ms11316 KiB
87Accepted9ms11564 KiB
88Accepted9ms11512 KiB
89Accepted9ms11316 KiB
90Wrong answer12ms11316 KiB
91Wrong answer74ms17564 KiB
92Wrong answer239ms25676 KiB
93Accepted224ms24660 KiB
94Accepted181ms27956 KiB
95Wrong answer9ms11500 KiB
96Accepted14ms11316 KiB
97Accepted26ms12852 KiB
98Wrong answer29ms13360 KiB
99Wrong answer28ms17460 KiB
100Accepted17ms15492 KiB
101Accepted17ms13364 KiB
102Accepted12ms12248 KiB
103Wrong answer13ms11320 KiB
104Accepted9ms11316 KiB
105Wrong answer10ms11584 KiB
106Wrong answer14ms11780 KiB
107Wrong answer16ms11572 KiB
108Wrong answer34ms14236 KiB
109Accepted39ms14384 KiB
110Accepted846ms125492 KiB
111Wrong answer233ms24884 KiB
112Time limit exceeded1.098s142660 KiB
113Time limit exceeded1.024s262144 KiB
114Time limit exceeded1.1s183968 KiB
115Time limit exceeded1.095s98088 KiB
116Time limit exceeded1.082s59720 KiB
117Time limit exceeded1.082s69192 KiB
118Runtime error686ms262144 KiB
119Runtime error578ms262144 KiB
120Wrong answer135ms18228 KiB
121Time limit exceeded1.1s178392 KiB
122Time limit exceeded1.103s184780 KiB
123Wrong answer171ms23156 KiB
124Wrong answer238ms24228 KiB
125Wrong answer179ms23076 KiB