oj.uz

Submission #826018

# Submission time Handle Problem Language Result Execution time Memory
826018 2023-08-15T09:55:21 Z vjudge1 Bosses (BOI16_bosses) C++17
67 / 100
 1500 ms 900 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;
}

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

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

    bst.push(u);

    u32 total = 0, cnt = 1;

    while (!bst.empty()) {
        auto tp = bst.front();
        bst.pop();
        visited[tp] = true;

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

    return cnt == n ? dfs_sz(total, adjc, u, u), 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
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 340 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 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 340 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 212 KB Output is correct
7 Correct 1 ms 212 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 212 KB Output is correct
11 Correct 1 ms 212 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 340 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 212 KB Output is correct
7 Correct 1 ms 212 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 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 4 ms 340 KB Output is correct
13 Correct 4 ms 340 KB Output is correct
14 Correct 380 ms 800 KB Output is correct
15 Correct 43 ms 716 KB Output is correct
16 Correct 1090 ms 848 KB Output is correct
17 Execution timed out 1580 ms 900 KB Time limit exceeded
18 Halted 0 ms 0 KB -