Submission #646564

#	Time	Username	Problem	Language	Result	Execution time	Memory
646564		Cyanmond	Friends (BOI17_friends)	C++17	100 / 100	568 ms	1712 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::map<int, int> que, const int r) -> void {
            if ((int)set.size() > P) return;
            if (r > Q) return;
            if ((int)set.size() + r + (int)que.size() > P + 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() -> first;
            --(que.begin() -> second);
            bool h = true;
            if (que.begin() -> second == 0) {
                h = false;
                que.erase(que.begin());
            }
            self(self, set, que, r + 1);
            
            if ((not group[c].empty()) and group[c].size() <= set.size()) {
                return;
            }
            if (h) que.erase(que.begin());
            set.insert(from);
            for (const int to : graph[from]) {
                if (set.find(to) == set.end()) {
                    ++que[to];
                }
            }
            self(self, set, que, r);
        };
        find(find, {}, {{c, 1}}, 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> ids;
    for (const int e : answer_index) {
        ids.insert(e);
    }
    const int K = (int)ids.size();

    std::vector<std::set<int>> sets;
    for (const int i : ids) {
        sets.push_back(group[i]);
    }

    auto judge = [&](const std::set<int> &s) -> bool {
        int cnt = 0;
        for (const int e : s) {
            for (const int to : graph[e]) {
                if (s.find(to) == s.end()) {
                    ++cnt;
                }
            }
        }
        return cnt <= Q;
    };

    for (int i = 0; i < K; ++i) {
        for (int j = i + 1; j < K; ++j) {
            auto &set_a = sets[i], &set_b = sets[j];

            auto itr_a = set_a.begin(), itr_b = set_b.begin();
            std::vector<int> common_elements;
            while (itr_a != set_a.end() and itr_b != set_b.end()) {
                if (*itr_a == *itr_b) {
                    common_elements.push_back(*itr_a);
                }
                if (*itr_a <= *itr_b) {
                    ++itr_a;
                } else {
                    ++itr_b;
                }
            }
            if (common_elements.empty()) {
                continue;
            }

            auto set_c = set_a;
            for (const int e : common_elements) {
                set_c.erase(e);
            }
            if (judge(set_c)) {
                set_a = set_c;
                continue;
            }

            set_c = set_b;
            for (const int e : common_elements) {
                set_c.erase(e);
            }
            if (judge(set_c)) {
                set_b = set_c;
                continue;
            }
        }
    }

    std::vector<std::set<int>> answer;
    for (const auto &e : sets) {
        if (e.empty()) {
            continue;
        }
        answer.push_back(e);
    }

    std::cout << "home" << std::endl;
    std::cout << answer.size() << std::endl;
    for (const auto &g : answer) {
        std::cout << g.size();
        for (const int e : g) {
            std::cout << ' ' << e;
        }
        std::cout << std::endl;
    }
}

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