161872025-04-13 18:02:13lacitoKét csoportcpp17Időlimit túllépés 61/100291ms34284 KiB
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> g;
vector<int> group, hate_cnt;
set<int> hate_set[4];

void update(int x, int cnt) {
    hate_set[hate_cnt[x]].erase(x);
    hate_cnt[x] = cnt;
    hate_set[cnt].insert(x);
}

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    g.resize(n + 1); group.resize(n + 1); hate_cnt.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        int x, cnt1 = 0;
        for (cin >> x; x != 0; cin >> x) {
            g[i].push_back(x);
            cnt1 += group[x];
        }
        if (cnt1 * 2 < g[i].size()) {
            group[i] = 1;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int x : g[i])
            hate_cnt[i] += (group[x] == group[i]);
        hate_set[hate_cnt[i]].insert(i);
    }
    while (hate_set[3].size() > 0 || hate_set[2].size() > 0) {
        int p = hate_set[3].size() > 0 ? *hate_set[3].begin() : *hate_set[2].begin();
        group[p] = 1 - group[p];
        update(p, g[p].size() - hate_cnt[p]);
        for (int x : g[p])
            update(x, group[x] == group[p] ? hate_cnt[x] + 1 : hate_cnt[x] - 1);
    }
    cout << count(group.begin() + 1, group.end(), 0) << endl;
    for (int i = 1; i <= n; i++)
        if (group[i] == 0)
            cout << i << " ";
    cout << endl;
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base61/100
1Elfogadva0/01ms316 KiB
2Elfogadva0/090ms11572 KiB
3Elfogadva3/31ms500 KiB
4Elfogadva3/31ms316 KiB
5Elfogadva3/31ms316 KiB
6Elfogadva3/31ms508 KiB
7Elfogadva3/31ms508 KiB
8Elfogadva2/21ms500 KiB
9Elfogadva3/32ms316 KiB
10Elfogadva3/32ms316 KiB
11Elfogadva3/32ms316 KiB
12Elfogadva3/39ms1332 KiB
13Elfogadva3/39ms1496 KiB
14Elfogadva3/310ms1516 KiB
15Elfogadva6/693ms11656 KiB
16Elfogadva7/797ms11652 KiB
17Elfogadva7/7114ms11572 KiB
18Elfogadva6/6188ms22908 KiB
19Időlimit túllépés0/6202ms23092 KiB
20Időlimit túllépés0/6237ms22836 KiB
21Időlimit túllépés0/6287ms34284 KiB
22Időlimit túllépés0/7282ms33844 KiB
23Időlimit túllépés0/7291ms33156 KiB
24Időlimit túllépés0/7279ms33076 KiB