258302026-03-04 21:16:21csdavidCsillagok bábeli tornyacpp17Wrong answer 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 << ' ';
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Wrong answer8ms11316 KiB
2Time limit exceeded1.093s205752 KiB
subtask20/10
3Accepted13ms11316 KiB
4Accepted9ms11316 KiB
5Accepted10ms11320 KiB
6Wrong answer13ms11316 KiB
7Accepted12ms11316 KiB
8Accepted9ms11500 KiB
9Wrong answer12ms11500 KiB
10Wrong answer9ms11316 KiB
11Wrong answer12ms11316 KiB
12Accepted10ms11560 KiB
subtask30/15
13Accepted12ms11316 KiB
14Accepted12ms11316 KiB
15Accepted9ms11336 KiB
16Accepted9ms11500 KiB
17Accepted112ms17200 KiB
18Time limit exceeded1.105s103476 KiB
19Time limit exceeded1.111s181196 KiB
20Time limit exceeded1.11s186800 KiB
21Time limit exceeded1.095s106068 KiB
22Time limit exceeded1.088s78772 KiB
23Time limit exceeded1.105s74548 KiB
24Time limit exceeded1.105s102964 KiB
25Accepted146ms20788 KiB
subtask40/10
26Accepted13ms11316 KiB
27Accepted10ms11316 KiB
28Accepted13ms11316 KiB
29Accepted10ms11252 KiB
30Accepted9ms11320 KiB
31Wrong answer9ms11300 KiB
32Wrong answer105ms17720 KiB
33Wrong answer317ms26688 KiB
34Accepted224ms25908 KiB
35Accepted324ms29236 KiB
subtask50/25
36Accepted13ms11316 KiB
37Accepted9ms11316 KiB
38Accepted10ms11320 KiB
39Wrong answer13ms11316 KiB
40Accepted12ms11316 KiB
41Accepted9ms11500 KiB
42Wrong answer12ms11500 KiB
43Wrong answer9ms11316 KiB
44Wrong answer12ms11316 KiB
45Accepted10ms11560 KiB
46Wrong answer9ms11336 KiB
47Accepted13ms11572 KiB
48Accepted43ms13108 KiB
49Wrong answer59ms13892 KiB
50Wrong answer27ms17280 KiB
51Accepted17ms15412 KiB
52Accepted14ms13288 KiB
53Accepted13ms12340 KiB
54Wrong answer13ms11520 KiB
55Accepted10ms11316 KiB
56Wrong answer12ms11384 KiB
57Wrong answer19ms12004 KiB
58Wrong answer17ms11828 KiB
59Wrong answer63ms14644 KiB
subtask60/40
60Wrong answer9ms11316 KiB
61Time limit exceeded1.098s177628 KiB
62Accepted13ms11316 KiB
63Accepted9ms11316 KiB
64Accepted10ms11320 KiB
65Wrong answer13ms11316 KiB
66Accepted12ms11316 KiB
67Accepted9ms11500 KiB
68Wrong answer12ms11500 KiB
69Wrong answer9ms11316 KiB
70Wrong answer12ms11316 KiB
71Accepted10ms11560 KiB
72Accepted12ms11316 KiB
73Accepted12ms11316 KiB
74Accepted9ms11336 KiB
75Accepted9ms11500 KiB
76Accepted112ms17200 KiB
77Time limit exceeded1.105s103476 KiB
78Time limit exceeded1.111s181196 KiB
79Time limit exceeded1.11s186800 KiB
80Time limit exceeded1.095s106068 KiB
81Time limit exceeded1.088s78772 KiB
82Time limit exceeded1.105s74548 KiB
83Time limit exceeded1.105s102964 KiB
84Accepted146ms20788 KiB
85Accepted13ms11316 KiB
86Accepted10ms11316 KiB
87Accepted13ms11316 KiB
88Accepted10ms11252 KiB
89Accepted9ms11320 KiB
90Wrong answer9ms11300 KiB
91Wrong answer105ms17720 KiB
92Wrong answer317ms26688 KiB
93Accepted224ms25908 KiB
94Accepted324ms29236 KiB
95Wrong answer9ms11336 KiB
96Accepted13ms11572 KiB
97Accepted43ms13108 KiB
98Wrong answer59ms13892 KiB
99Wrong answer27ms17280 KiB
100Accepted17ms15412 KiB
101Accepted14ms13288 KiB
102Accepted13ms12340 KiB
103Wrong answer13ms11520 KiB
104Accepted10ms11316 KiB
105Wrong answer12ms11384 KiB
106Wrong answer19ms12004 KiB
107Wrong answer17ms11828 KiB
108Wrong answer63ms14644 KiB
109Accepted64ms14892 KiB
110Time limit exceeded1.093s120116 KiB
111Wrong answer296ms26416 KiB
112Time limit exceeded1.098s218616 KiB
113Time limit exceeded1.095s245712 KiB
114Time limit exceeded1.093s140800 KiB
115Time limit exceeded1.106s130544 KiB
116Time limit exceeded1.082s73264 KiB
117Time limit exceeded1.093s75392 KiB
118Runtime error691ms262144 KiB
119Runtime error680ms262144 KiB
120Wrong answer180ms18220 KiB
121Time limit exceeded1.093s188420 KiB
122Time limit exceeded1.095s233576 KiB
123Wrong answer298ms24312 KiB
124Wrong answer312ms25652 KiB
125Wrong answer247ms22836 KiB