oj.uz

Submission #826050

# Submission time Handle Problem Language Result Execution time Memory
826050 2023-08-15T10:04:40 Z vjudge1 Bosses (BOI16_bosses) C++17
100 / 100
 403 ms 724 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::vector<u32> cost;

u32 bfs(u32 n, const AdjList& adj, u32 u) {
    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]) {
                cnt++;
                cost[v] = cost[tp] + 1;
                total += cost[v];
                bfsq.push(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) {
        cost.assign(n, 0);
        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 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 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 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 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 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct

Subtask #3
33.0 / 33.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 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 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 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 2 ms 328 KB Output is correct
14 Correct 84 ms 508 KB Output is correct
15 Correct 17 ms 580 KB Output is correct
16 Correct 403 ms 644 KB Output is correct
17 Correct 383 ms 584 KB Output is correct
18 Correct 389 ms 724 KB Output is correct