oj.uz

Submission #826029

# Submission time Handle Problem Language Result Execution time Memory
826029 2023-08-15T09:58:53 Z vjudge1 Bosses (BOI16_bosses) C++17
67 / 100
 1500 ms 864 KB 
#include <bits/stdc++.h>

// #ifndef LOCAL
// #pragma GCC optimize("O3,no-stack-protector,unroll-loops")
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
// #endif

typedef unsigned short u16;
typedef short i16;
typedef unsigned int u32;
typedef int i32;
typedef unsigned long long u64;
typedef long long i64;
typedef float f32;
typedef double f64;
typedef long double f80;
typedef long double f128;

template <typename T>
using limits = std::numeric_limits<T>;

#ifdef LOCAL
#include "tools.hpp"
#define here(...)                                                                \
    std::cerr << __func__ << ':' << __LINE__ << " [" << #__VA_ARGS__ << "] = ["; \
    _debug(__VA_ARGS__)
#else
#define here(...)
#endif

namespace std {
    template <typename T, typename U>
    struct hash<pair<T, U>> {
        size_t operator()(const pair<T, U>& x) const { return hash<T>()(x.first) ^ hash<U>()(x.second); }
    };
}  // namespace std

struct custom_hash {
    static u64 splitmix64(u64 x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    std::size_t operator()(u64 x) const {
        static const u64 rand_time = static_cast<u64>(std::chrono::steady_clock::now().time_since_epoch().count());
        return splitmix64(x + rand_time);
    }

    template <typename T, typename U>
    std::size_t operator()(const std::pair<T, U>& x) const {
        return splitmix64((*this)(x.first) ^ (*this)(x.second));
    }
};

typedef std::vector<std::vector<u32>> AdjList;

u32 dfs_sz(u32& total, const AdjList& adjc, u32 u, u32 prev) {
    u32 res = 1;
    for (auto& v : adjc[u]) {
        if (v != prev) {
            res += dfs_sz(total, adjc, v, u);
        }
    }
    total += res;
    return res;
}

template <typename T>
std::vector<T> with_capacity(u64 sz) {
    std::vector<T> res;
    res.reserve(sz);
    return res;
}

const u32 UDEF = limits<u32>::max();

u32 bfs(u32 n, const AdjList& adj, u32 u) {
    AdjList adjc(n, with_capacity<u32>(n));
    std::vector<u32> cost(n);
    std::queue<u32> bst;

    bst.push(u);
    cost[u] = 1;

    u32 total = 1, cnt = 1;

    while (!bst.empty()) {
        auto tp = bst.front();
        bst.pop();

        for (auto& v : adj[tp]) {
            if (!cost[v]) {
                bst.push(v);
                adjc[tp].push_back(v);
                cnt++;
                cost[v] = cost[tp] + 1;
                total += cost[v];
            }
        }
    }

    return cnt == n ? total : UDEF;
}

void solve() {
    u32 n;
    std::cin >> n;
    AdjList adj(n, with_capacity<u32>(n));

    for (u32 i = 0; i < n; ++i) {
        u32 k;
        std::cin >> k;
        while (k--) {
            u32 pi;
            std::cin >> pi;
            pi--;
            adj[pi].push_back(i);
        }
    }

    u32 tres = UDEF;

    for (u32 i = 0; i < n; ++i) {
        tres = std::min(tres, bfs(n, adj, i));
    }

    std::cout << tres << '\n';
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#ifdef LOCAL
    std::ifstream input("./in.txt");
    std::ofstream output("./log/bsol.txt");
    auto cin_buf = std::cin.rdbuf(input.rdbuf());
    auto cout_buf = std::cout.rdbuf(output.rdbuf());
#endif
    solve();
#ifdef LOCAL
    std::cin.rdbuf(cin_buf);
    std::cout.rdbuf(cout_buf);
    input.close();
    output.close();
#endif
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 4 ms 328 KB Output is correct
13 Correct 3 ms 332 KB Output is correct
14 Correct 415 ms 724 KB Output is correct
15 Correct 80 ms 700 KB Output is correct
16 Correct 1186 ms 864 KB Output is correct
17 Execution timed out 1563 ms 852 KB Time limit exceeded
18 Halted 0 ms 0 KB -