Submission #1260509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260509		gary	Bosses (BOI16_bosses)	C++20	100 / 100	861 ms	1216 KiB

bosses

// BOI 2016 Bosses

#include <bits/stdc++.h>

using namespace std;

#define int long long

// #define GARY_DBG
#define GARY_LIB
#ifdef GARY_DBG

#ifndef GARY_LIB
#include <bits/stdc++.h>
#endif

// --- ANSI Color Codes ---
#define RESET "\033[0m"
#define RED "\033[31m" /* Red */
#define GREEN "\033[32m" /* Green */
#define YELLOW "\033[33m" /* Yellow */
#define BLUE "\033[34m" /* Blue */
#define MAGENTA "\033[35m" /* Magenta */
#define CYAN "\033[36m" /* Cyan */

// Overload for std::pair
template<typename T, typename U>
std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) {
    return os << '(' << p.first << ", " << p.second << ')';
}

// For std::tuple
template<typename... Ts>
std::ostream& operator<<(std::ostream& os, const std::tuple<Ts...>& t) {
    os << '(';
    std::apply(
        [&os](const auto&... args) {
            bool first = true;
            ((os << (first ? "" : ", ") << args, first = false), ...);
        },
        t);
    return os << ')';
}

//  For std::bitset
template<size_t N>
std::ostream& operator<<(std::ostream& os, const std::bitset<N>& b) {
    return os << "bitset{" << b.to_string() << "}";
}

// Helper trait to detect if a type is a string
template<typename T>
struct is_string : std::false_type {};
template<>
struct is_string<std::string> : std::true_type {};
template<>
struct is_string<const char*> : std::true_type {};
template<>
struct is_string<char*> : std::true_type {};

// Overload for std::stack
// We pass by value to create a copy that we can pop from.
template<typename T, typename Container>
std::ostream& operator<<(std::ostream& os, std::stack<T, Container> s) {
    os << "stack{top: ";
    bool first = true;
    while (!s.empty()) {
        if (!first) os << ", ";
        first = false;
        os << s.top();
        s.pop();
    }
    os << '}';
    return os;
}

// Overload for std::queue
// We pass by value to create a copy that we can pop from.
template<typename T, typename Container>
std::ostream& operator<<(std::ostream& os, std::queue<T, Container> q) {
    os << "queue{front: ";
    bool first = true;
    while (!q.empty()) {
        if (!first) os << ", ";
        first = false;
        os << q.front();
        q.pop();
    }
    os << '}';
    return os;
}

// Overload for std::priority_queue
// We pass by value to create a copy that we can pop from.
template<typename T, typename Container, typename Compare>
std::ostream& operator<<(std::ostream& os, std::priority_queue<T, Container, Compare> pq) {
    os << "pq{top: ";
    bool first = true;
    while (!pq.empty()) {
        if (!first) os << ", ";
        first = false;
        os << pq.top();
        pq.pop();
    }
    os << '}';
    return os;
}

// Overload for containers (like vector, list, set, map, and deque) excluding strings
template<typename Container, typename std::enable_if<!is_string<Container>::value && !std::is_same<Container, std::string>::value &&
                                                         !std::is_same<Container, const char*>::value && !std::is_same<Container, char*>::value &&
                                                         !std::is_same<typename Container::value_type, char>::value,
                                                     int>::type = 0>
std::ostream& operator<<(std::ostream& os, const Container& container) {
    os << '{';
    bool first = true;
    for (const auto& elem : container) {
        if (!first) os << ", ";
        first = false;
        os << elem;
    }
    os << '}';
    return os;
}

// Helper to print multiple arguments (tuple unpacking trick)
template<size_t Index = 0, typename... Ts>
typename std::enable_if<Index == sizeof...(Ts)>::type print_tuple(const std::tuple<Ts...>&) {
}

template<size_t Index = 0, typename... Ts>
    typename std::enable_if < Index<sizeof...(Ts)>::type print_tuple(const std::tuple<Ts...>& t) {
    if (Index > 0) std::cerr << ", ";
    std::cerr << std::get<Index>(t);
    print_tuple<Index + 1>(t);
}

// Debug macro
#define debug(...)                                                                                                 \
    do {                                                                                                           \
        std::cerr << MAGENTA << "[" << __FILE__ << ":" << __LINE__ << " (" << __func__ << ")]" << RESET << " -> "; \
        std::cerr << "[" << #__VA_ARGS__ << "] ~> [";                                                              \
        print_tuple(std::make_tuple(__VA_ARGS__));                                                                 \
        std::cerr << "]\n";                                                                                        \
    } while (0)
#else
#define debug(...) ((void)0)
#endif

constexpr int sizik = 5 * 1001;

#define ar std::array
#define pr std::pair
#define vec std::vector

typedef vec<vec<int>> _kra;

int n;
std::vector<int> kra[sizik];
int curr = 1;
int visited[sizik];
int parent[sizik];
std::vector<int> kra1[sizik];
// O(n + S)
void clear() {
    for (int i = 1; i <= n; i++) {
        parent[i] = 0;
        kra1[i].clear();
    }
}
// O(n+S)
void BFS(int v) {
    clear();

    std::queue<ar<int, 2>> q;
    q.push({v, 0});
    while (!q.empty()) {
        const auto [u, p] = q.front();
        q.pop();
        assert(1 <= u && u <= n);
        if (visited[u] == curr) continue;
        visited[u] = curr;
        parent[u] = p;
        kra1[p].push_back(u);
        for (const auto& y : kra[u]) {
            q.push({y, u});
        }
    }
}
int total_cost = 0;
int DFS(int v) {
    int q = 1;
    for (const auto& u : kra1[v]) {
        if (u != parent[v]) {
            q += DFS(u);
        }
    }
    total_cost += q;
    debug(v, q);
    return q;
}
int calc_cost(int root) {
    // check if good tree..
    int z = 0;
    for (int i = 1; i <= n; i++) {
        z += kra1[i].size();
    }
    if (z != n - 1) {
        // not tree . kamo.. co děláš?
        return INT64_MAX;
    }

    total_cost = 0;
    // dfs helper bro
    DFS(root);
    return total_cost;
}

void solve() {
    std::cin >> n;

    for (int i = 1; i <= n; i++) {
        int a;
        std::cin >> a;

        for (int j = 0; j < a; j++) {
            int b;
            std::cin >> b;

            // i -> b

            // b -> i
            kra[b].push_back(i);
        }
    }

    int ans = INT64_MAX;
    for (int i = 1; i <= n; i++) {
        curr++;
        BFS(i);
        int local_cost = calc_cost(i);
        ans = std::min(ans, local_cost);
#ifdef GARY_DBG
        for (int j = 1; j <= n; j++) {
            // debug(i, j, kra1[j]);
            for (const auto& a : kra1[j]) {
                std::cout << j << " " << a << std::endl;
            }
        }
#endif
        debug(i, local_cost);
    }
    std::cout << ans << std::endl;
}

int32_t main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33