191802025-11-28 14:31:56szilCsillagok bábeli tornyacpp17Accepted 100/100289ms22764 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 100'001;

int b[MAXN], scc[MAXN], timer = 1;
bool vis[MAXN], vis2[MAXN];
vector<pair<int, int>> g[MAXN], g2[MAXN];
vector<int> comp;
stack<int> st;

void dfs(int u) {
    vis[u] = 1;
    for (auto [v, tmp] : g[u]) {
        if (!vis[v]) dfs(v);
    }
    st.push(u);
}

void dfs2(int u, int cc) {
    vis2[u] = 1;
    scc[u] = cc;
    comp.emplace_back(u);
    for (auto [v, tmp] : g2[u]) {
        if (!vis2[v]) dfs2(v, cc);
    }
}

int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) {
        int k; cin >> k;
        g[b[i]].emplace_back(b[i], i);
        g2[b[i]].emplace_back(b[i], i);
        for (int j = 0; j < k; j++) {
            int x; cin >> x;
            g[x].emplace_back(b[i], i);
            g2[b[i]].emplace_back(x, i);
        }
    }
    for (int i = 1; i <= m; i++) {
        if (!vis[i]) dfs(i);
    }
    vector<int> ans;
    while (!st.empty()) {
        int u = st.top();
        st.pop();
        if (vis2[u]) continue;
        comp.clear();
        dfs2(u, timer++);
        set<int> curr;
        for (int v : comp) {
            for (auto [x, idx] : g2[v]) {
                if (scc[x] == scc[v]) {
                    curr.insert(idx);
                }
            }
        }
        if (curr.size() > ans.size()) {
            ans.clear();
            for (int x : curr) ans.emplace_back(x);
        }
    }
    cout << ans.size() << "\n";
    for (int x : ans) cout << x << " ";
    cout << "\n";
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted4ms5112 KiB
2Accepted23ms7220 KiB
subtask210/10
3Accepted6ms5224 KiB
4Accepted4ms4916 KiB
5Accepted6ms5296 KiB
6Accepted4ms4916 KiB
7Accepted4ms4916 KiB
8Accepted6ms4916 KiB
9Accepted6ms4916 KiB
10Accepted6ms4916 KiB
11Accepted4ms5172 KiB
12Accepted6ms5172 KiB
subtask315/15
13Accepted4ms4916 KiB
14Accepted4ms4916 KiB
15Accepted6ms5124 KiB
16Accepted6ms4916 KiB
17Accepted39ms7228 KiB
18Accepted37ms7412 KiB
19Accepted90ms13628 KiB
20Accepted76ms10652 KiB
21Accepted70ms9544 KiB
22Accepted57ms8520 KiB
23Accepted59ms8244 KiB
24Accepted57ms7988 KiB
25Accepted97ms11572 KiB
subtask410/10
26Accepted6ms4932 KiB
27Accepted4ms4916 KiB
28Accepted4ms4920 KiB
29Accepted4ms4916 KiB
30Accepted4ms4916 KiB
31Accepted6ms4916 KiB
32Accepted72ms9500 KiB
33Accepted163ms15400 KiB
34Accepted272ms15216 KiB
35Accepted289ms22764 KiB
subtask525/25
36Accepted6ms5224 KiB
37Accepted4ms4916 KiB
38Accepted6ms5296 KiB
39Accepted4ms4916 KiB
40Accepted4ms4916 KiB
41Accepted6ms4916 KiB
42Accepted6ms4916 KiB
43Accepted6ms4916 KiB
44Accepted4ms5172 KiB
45Accepted6ms5172 KiB
46Accepted4ms5108 KiB
47Accepted8ms5428 KiB
48Accepted34ms7732 KiB
49Accepted54ms9732 KiB
50Accepted7ms5152 KiB
51Accepted4ms5172 KiB
52Accepted6ms5184 KiB
53Accepted7ms4916 KiB
54Accepted6ms5172 KiB
55Accepted7ms5172 KiB
56Accepted7ms5268 KiB
57Accepted13ms5732 KiB
58Accepted12ms5684 KiB
59Accepted59ms9804 KiB
subtask640/40
60Accepted4ms4916 KiB
61Accepted25ms6964 KiB
62Accepted6ms5224 KiB
63Accepted4ms4916 KiB
64Accepted6ms5296 KiB
65Accepted4ms4916 KiB
66Accepted4ms4916 KiB
67Accepted6ms4916 KiB
68Accepted6ms4916 KiB
69Accepted6ms4916 KiB
70Accepted4ms5172 KiB
71Accepted6ms5172 KiB
72Accepted4ms4916 KiB
73Accepted4ms4916 KiB
74Accepted6ms5124 KiB
75Accepted6ms4916 KiB
76Accepted39ms7228 KiB
77Accepted37ms7412 KiB
78Accepted90ms13628 KiB
79Accepted76ms10652 KiB
80Accepted70ms9544 KiB
81Accepted57ms8520 KiB
82Accepted59ms8244 KiB
83Accepted57ms7988 KiB
84Accepted97ms11572 KiB
85Accepted6ms4932 KiB
86Accepted4ms4916 KiB
87Accepted4ms4920 KiB
88Accepted4ms4916 KiB
89Accepted4ms4916 KiB
90Accepted6ms4916 KiB
91Accepted72ms9500 KiB
92Accepted163ms15400 KiB
93Accepted272ms15216 KiB
94Accepted289ms22764 KiB
95Accepted4ms5108 KiB
96Accepted8ms5428 KiB
97Accepted34ms7732 KiB
98Accepted54ms9732 KiB
99Accepted7ms5152 KiB
100Accepted4ms5172 KiB
101Accepted6ms5184 KiB
102Accepted7ms4916 KiB
103Accepted6ms5172 KiB
104Accepted7ms5172 KiB
105Accepted7ms5268 KiB
106Accepted13ms5732 KiB
107Accepted12ms5684 KiB
108Accepted59ms9804 KiB
109Accepted59ms10288 KiB
110Accepted112ms13192 KiB
111Accepted187ms17392 KiB
112Accepted85ms11460 KiB
113Accepted45ms8232 KiB
114Accepted75ms10528 KiB
115Accepted72ms9624 KiB
116Accepted59ms8500 KiB
117Accepted57ms7988 KiB
118Accepted14ms5940 KiB
119Accepted52ms9248 KiB
120Accepted151ms13620 KiB
121Accepted97ms13768 KiB
122Accepted97ms13800 KiB
123Accepted158ms14376 KiB
124Accepted166ms14640 KiB
125Accepted203ms14384 KiB