oj.uz

Submission #826032

# Submission time Handle Problem Language Result Execution time Memory
826032 2023-08-15T10:01:45 Z vjudge1 Bosses (BOI16_bosses) C++17
67 / 100
 1500 ms 832 KB 
#include <bits/stdc++.h>

#ifndef LOCAL
#pragma GCC optimize("Ofast,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();

std::queue<u32> bfsq;
std::unordered_map<u32, u32, custom_hash> cost;

u32 bfs(u32 n, const AdjList& adj, u32 u) {
    cost.clear();

    u32 total = 1, cnt = 1;
    bfsq.push(u);
    cost[u] = 1;

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

        for (auto& v : adj[tp]) {
            if (!cost[v]) {
                bfsq.push(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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #2
45.0 / 45.0

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

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 2 ms 316 KB Output is correct
12 Correct 49 ms 432 KB Output is correct
13 Correct 32 ms 340 KB Output is correct
14 Correct 766 ms 732 KB Output is correct
15 Correct 9 ms 748 KB Output is correct
16 Execution timed out 1520 ms 832 KB Time limit exceeded
17 Halted 0 ms 0 KB -