oj.uz

Submission #645712

# Submission time Handle Problem Language Result Execution time Memory
645712 2022-09-27T17:23:14 Z Cyanmond Friends (BOI17_friends) C++17
0 / 100
 2 ms 212 KB 
#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 > 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();
            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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 2 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 2 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -