oj.uz

Submission #825922

# Submission time Handle Problem Language Result Execution time Memory
825922 2023-08-15T09:22:35 Z vjudge1 Bosses (BOI16_bosses) C++17
0 / 100
 0 ms 212 KB 
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#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;
}

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

u32 bfs(u32 n, const AdjList& adj, u32 u) {
    AdjList adjc(n);
    std::unordered_map<u32, bool, custom_hash> visited;
    std::stack<u32> bst;

    u32 total = 0, cnt = 1;

    bst.push(u);
    visited[u] = true;

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

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

    dfs_sz(total, adjc, u, UDEF);

    return cnt == n ? total : UDEF;
}

void solve() {
    u32 n;
    std::cin >> n;
    AdjList adj(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
0 / 22.0

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 33.0

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