96852024-02-26 15:30:53norbertvidaParti (75 pont)cpp11Időlimit túllépés 72/75400ms6804 KiB
#include <bits/stdc++.h>

#define MAX_N 100000
int N;
int edgesA[MAX_N], edgesB[MAX_N];
int invitee_counter[MAX_N];

using namespace std;

int main() {
    iostream::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for(int i = 0, a, b; i < N; ++i) {
        cin >> a >> b;
        --a;
        --b;
        edgesA[i] = a;
        edgesB[i] = b;
        ++invitee_counter[a];
        ++invitee_counter[b];
    }
    vector<int> nodes;
    for(int i = N - 1; i >= 0; --i) {
        if(invitee_counter[i] < 2) {
            --invitee_counter[edgesA[i]];
            --invitee_counter[edgesB[i]];
            continue;
        }
        nodes.push_back(i);
    }
    while(true) {
        sort(nodes.begin(), nodes.end(), [&](int a, int b) {
            return invitee_counter[a] > invitee_counter[b];
        });
        if(invitee_counter[*nodes.rbegin()] >= 2) break;
        for(auto it = nodes.rbegin(); it != nodes.rend(); ++it) {
            if(invitee_counter[*it] >= 2) break;
            --invitee_counter[edgesA[*it]];
            --invitee_counter[edgesB[*it]];
            nodes.pop_back();
        }
    }
    sort(nodes.begin(), nodes.end());
    cout << nodes.size() << "\n";
    for(auto n : nodes) cout << n + 1 << " ";
    cout << "\n";
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base72/75
1Elfogadva0/03ms1836 KiB
2Elfogadva0/019ms3680 KiB
3Elfogadva3/33ms2392 KiB
4Elfogadva3/33ms2608 KiB
5Időlimit túllépés0/3400ms2928 KiB
6Elfogadva3/33ms2932 KiB
7Elfogadva3/33ms2856 KiB
8Elfogadva4/43ms3120 KiB
9Elfogadva4/43ms3336 KiB
10Elfogadva4/43ms3312 KiB
11Elfogadva4/43ms3448 KiB
12Elfogadva4/43ms3320 KiB
13Elfogadva4/43ms3340 KiB
14Elfogadva4/44ms3352 KiB
15Elfogadva4/419ms5076 KiB
16Elfogadva4/423ms5332 KiB
17Elfogadva4/427ms5768 KiB
18Elfogadva4/429ms6144 KiB
19Elfogadva4/434ms6388 KiB
20Elfogadva4/437ms6804 KiB
21Elfogadva4/437ms6772 KiB
22Elfogadva4/43ms3952 KiB