86132024-01-23 16:28:43Wrinkle1564Kerékpártúra (50 pont)cpp17Hibás válasz 21/50294ms25104 KiB
#include <algorithm>
#include <iostream>
#include <set>
#include <unordered_map>

using std::cin;
using std::cout;
using std::set;
using std::unordered_map;

// 2 `set`s, one has any of the other one
auto contains(const set<int> &has, const set<int> &any) -> bool {
    for (const auto &item : has) {
        if (any.find(item) != any.end()) {
            return true;
        }
    }
    return false;
}

auto main() -> int {
    // num of all points
    int n = 0;
    cin >> n;
    // num of routes
    int m = 0;
    cin >> m;
    // idx+1 of starting point
    int k = 0;
    cin >> k;

    // the hashmap containing information about the map
    unordered_map<int, set<int>> umap;

    int from = 0;
    int to = 0;
    for (int i = 0; i < m; i++) {
        cin >> from >> to;
        // inserting to `from`-s set
        umap[from].insert(to);
    }

    // the `set` containing points, from where you can access `k`
    set<int> can_access_k;
    // adding items, that can go to `k`
    for (const auto &item : umap) {
        // if `item`s destinations contains `k` or `v` contains any of `item`s
        // destinations
        if (item.second.find(k) != item.second.end() || contains(can_access_k, item.second)) {
            can_access_k.insert(item.first);
        }
    }
    // deleting `k`
    can_access_k.erase(k);

    // the `set` containing possible end points
    set<int> ends;

    // iterating through `v`
    for (const auto &item : can_access_k) {
        // inserting `item`
        ends.insert(item);
        // inserting every item of `item`s destinations
        for (const auto &it : umap[item]) {
            ends.insert(it);
        }
    }
    // inserting everyone of `k`-s direct neighbours
    for (const auto &item : umap[k]) {
        ends.insert(item);
    }
    // and finally deleting `k` itself
    ends.erase(k);

    cout << ends.size() << "\n";
    for (const auto &end : ends) {
        cout << end << " ";
    }

    cout << std::endl;
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base21/50
1Elfogadva0/03ms1812 KiB
2Elfogadva0/028ms6104 KiB
3Hibás válasz0/22ms2140 KiB
4Hibás válasz0/22ms2088 KiB
5Hibás válasz0/23ms2228 KiB
6Elfogadva2/23ms2328 KiB
7Elfogadva2/23ms2600 KiB
8Elfogadva2/24ms2796 KiB
9Hibás válasz0/24ms2900 KiB
10Hibás válasz0/26ms3080 KiB
11Hibás válasz0/27ms3460 KiB
12Elfogadva2/217ms4832 KiB
13Elfogadva2/217ms4636 KiB
14Elfogadva2/232ms6580 KiB
15Hibás válasz0/339ms8868 KiB
16Hibás válasz0/443ms9364 KiB
17Hibás válasz0/463ms11556 KiB
18Hibás válasz0/354ms11028 KiB
19Hibás válasz0/346ms10396 KiB
20Elfogadva3/3192ms21928 KiB
21Elfogadva3/3294ms24632 KiB
22Elfogadva3/3204ms25104 KiB