Submission #645711

#	Time	Username	Problem	Language	Result	Execution time	Memory
645711		Cyanmond	Friends (BOI17_friends)	C++17	0 / 100	1 ms	212 KiB

friends

#include <bits/stdc++.h>

int main() {
    int N, P, Q;
    std::cin >> N >> P >> Q;

    std::vector<int> M(N);
    std::vector<std::vector<int>> graph(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> M[i];
        graph[i].resize(M[i]);
        for (int &e : graph[i]) {
            std::cin >> e;
        }
    }

    // check : input is valid ?
    {
        std::set<std::pair<int, int>> s;
        for (int i = 0; i < N; ++i) {
            for (const int e : graph[i]) {
                const auto pair = std::minmax(i, e);
                if (s.find(pair) == s.end()) {
                    s.insert(pair);
                } else {
                    s.erase(pair);
                }
            }
        }

        if (not s.empty()) {
            std::cout << "detention" << std::endl;
            return 0;
        }
    }

    std::vector<std::set<int>> group(N);
    for (int c = 0; c < N; ++c) {
        auto find = [&](auto &&self, std::set<int> set, std::multiset<int> que, const int r) -> void {
            if ((int)set.size() > P) return;
            if (r + (int)que.size() > Q) return;

            if (que.empty()) {
                if (set.empty()) {
                    return;
                }
                if (group[c].empty() or group[c].size() > set.size()) {
                    group[c] = set;
                }
                return;
            }

            const int from = *que.begin();
            que.erase(que.begin());
            self(self, set, que, r + 1);
            
            if ((not group[c].empty()) and group[c].size() <= set.size()) {
                return;
            }
            que.erase(from);
            set.insert(from);
            for (const int to : graph[from]) {
                if (set.find(to) == set.end()) {
                    que.insert(to);
                }
            }
            self(self, set, que, r);
        };
        find(find, {}, {c}, 0);
    }

    if (std::any_of(group.begin(), group.end(), [&](const auto &e) { return e.empty(); })) {
        std::cout << "detention" << std::endl;
        return 0;
    }

    std::vector<int> answer_index(N, -1);
    for (int i = 0; i < N; ++i) {
        for (const int e : group[i]) {
            int &x = answer_index[e];
            if (x == -1 or group[x].size() < group[i].size()) {
                x = i;
            }
        }
    }

    std::set<int> answer;
    for (const int e : answer_index) {
        answer.insert(e);
    }
    
    std::cout << "home" << std::endl;
    std::cout << answer.size() << std::endl;
    for (const int i : answer) {
        std::cout << group[i].size();
        for (const int e : group[i]) {
            std::cout << ' ' << e;
        }
        std::cout << std::endl;
    }
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 37
• Subtask 3: 0 / 12
• Subtask 4: 0 / 31