191802025-11-28 14:31:56szilCsillagok bábeli tornyacpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva4ms5112 KiB
2Elfogadva23ms7220 KiB
subtask210/10
3Elfogadva6ms5224 KiB
4Elfogadva4ms4916 KiB
5Elfogadva6ms5296 KiB
6Elfogadva4ms4916 KiB
7Elfogadva4ms4916 KiB
8Elfogadva6ms4916 KiB
9Elfogadva6ms4916 KiB
10Elfogadva6ms4916 KiB
11Elfogadva4ms5172 KiB
12Elfogadva6ms5172 KiB
subtask315/15
13Elfogadva4ms4916 KiB
14Elfogadva4ms4916 KiB
15Elfogadva6ms5124 KiB
16Elfogadva6ms4916 KiB
17Elfogadva39ms7228 KiB
18Elfogadva37ms7412 KiB
19Elfogadva90ms13628 KiB
20Elfogadva76ms10652 KiB
21Elfogadva70ms9544 KiB
22Elfogadva57ms8520 KiB
23Elfogadva59ms8244 KiB
24Elfogadva57ms7988 KiB
25Elfogadva97ms11572 KiB
subtask410/10
26Elfogadva6ms4932 KiB
27Elfogadva4ms4916 KiB
28Elfogadva4ms4920 KiB
29Elfogadva4ms4916 KiB
30Elfogadva4ms4916 KiB
31Elfogadva6ms4916 KiB
32Elfogadva72ms9500 KiB
33Elfogadva163ms15400 KiB
34Elfogadva272ms15216 KiB
35Elfogadva289ms22764 KiB
subtask525/25
36Elfogadva6ms5224 KiB
37Elfogadva4ms4916 KiB
38Elfogadva6ms5296 KiB
39Elfogadva4ms4916 KiB
40Elfogadva4ms4916 KiB
41Elfogadva6ms4916 KiB
42Elfogadva6ms4916 KiB
43Elfogadva6ms4916 KiB
44Elfogadva4ms5172 KiB
45Elfogadva6ms5172 KiB
46Elfogadva4ms5108 KiB
47Elfogadva8ms5428 KiB
48Elfogadva34ms7732 KiB
49Elfogadva54ms9732 KiB
50Elfogadva7ms5152 KiB
51Elfogadva4ms5172 KiB
52Elfogadva6ms5184 KiB
53Elfogadva7ms4916 KiB
54Elfogadva6ms5172 KiB
55Elfogadva7ms5172 KiB
56Elfogadva7ms5268 KiB
57Elfogadva13ms5732 KiB
58Elfogadva12ms5684 KiB
59Elfogadva59ms9804 KiB
subtask640/40
60Elfogadva4ms4916 KiB
61Elfogadva25ms6964 KiB
62Elfogadva6ms5224 KiB
63Elfogadva4ms4916 KiB
64Elfogadva6ms5296 KiB
65Elfogadva4ms4916 KiB
66Elfogadva4ms4916 KiB
67Elfogadva6ms4916 KiB
68Elfogadva6ms4916 KiB
69Elfogadva6ms4916 KiB
70Elfogadva4ms5172 KiB
71Elfogadva6ms5172 KiB
72Elfogadva4ms4916 KiB
73Elfogadva4ms4916 KiB
74Elfogadva6ms5124 KiB
75Elfogadva6ms4916 KiB
76Elfogadva39ms7228 KiB
77Elfogadva37ms7412 KiB
78Elfogadva90ms13628 KiB
79Elfogadva76ms10652 KiB
80Elfogadva70ms9544 KiB
81Elfogadva57ms8520 KiB
82Elfogadva59ms8244 KiB
83Elfogadva57ms7988 KiB
84Elfogadva97ms11572 KiB
85Elfogadva6ms4932 KiB
86Elfogadva4ms4916 KiB
87Elfogadva4ms4920 KiB
88Elfogadva4ms4916 KiB
89Elfogadva4ms4916 KiB
90Elfogadva6ms4916 KiB
91Elfogadva72ms9500 KiB
92Elfogadva163ms15400 KiB
93Elfogadva272ms15216 KiB
94Elfogadva289ms22764 KiB
95Elfogadva4ms5108 KiB
96Elfogadva8ms5428 KiB
97Elfogadva34ms7732 KiB
98Elfogadva54ms9732 KiB
99Elfogadva7ms5152 KiB
100Elfogadva4ms5172 KiB
101Elfogadva6ms5184 KiB
102Elfogadva7ms4916 KiB
103Elfogadva6ms5172 KiB
104Elfogadva7ms5172 KiB
105Elfogadva7ms5268 KiB
106Elfogadva13ms5732 KiB
107Elfogadva12ms5684 KiB
108Elfogadva59ms9804 KiB
109Elfogadva59ms10288 KiB
110Elfogadva112ms13192 KiB
111Elfogadva187ms17392 KiB
112Elfogadva85ms11460 KiB
113Elfogadva45ms8232 KiB
114Elfogadva75ms10528 KiB
115Elfogadva72ms9624 KiB
116Elfogadva59ms8500 KiB
117Elfogadva57ms7988 KiB
118Elfogadva14ms5940 KiB
119Elfogadva52ms9248 KiB
120Elfogadva151ms13620 KiB
121Elfogadva97ms13768 KiB
122Elfogadva97ms13800 KiB
123Elfogadva158ms14376 KiB
124Elfogadva166ms14640 KiB
125Elfogadva203ms14384 KiB